Линейные рекуррентные соотношения первого порядка с переменным коэффициентом.К числу,
Линейные рекуррентные соотношения первого порядка с переменным коэффициентом.
К числу, сначало равному нулю, прибавляется шаг за шагом по единице до получения значения , . Докажите, что при этом будет нужно переносов единицы в старший разряд.
1 ответ
Элина Бибулатова
Для подтверждения можно использовать индукцию.
Но формулу 2^n - n - 1 можно вывести, исходя лишь из условия задачки. Обозначим через S(n) исследуемое количество переносов и зацелим, что если прибавлением единиц теснее получено число 2^n-1 - 1 (на это потребуется S(n-l) переносов), то еще одно прибавление единицы востребует n - 1 переносов и приведет к числу 2^n-1, двоичная запись которого есть 10...0 (количество нулей после единицы равно n-1).
Далее в процессе достижения числа 11...1 (n единиц) потребуется еще S(n-l) переносов. Получаем рекуррентное уравнение S(n) = 2S(n - 1) + n - 1 или
S(n)-2S(n-l) = n-l, (1)
при этом s(0) = 0.
Характеристическое уравнение, подходящее рекуррентному уравнению (1), имеет вид А - 2 = 0. Общее решение однородного уравнения S(n) - 2S(n - 1) = 0 есть сТ.
Правую часть уравнения (1) можно записать в виде квазиполинома (n-1)*n. Значение 1 не является корнем характеристического уравнения, поэтому (ур. 1) владеет приватным решением вида an + X; подставляя это выражение вместо s(n) в (1), получаем an + X - 2(а(n - 1) + X) = n - 1, и, приравнивая в левой и правой долях коэффициенты при первой и нулевой ступенях n, имеем а = X = -1. Получаем общее решение уравнения (1): S(n) = C2^n- n- 1. Подбираем значение константы стак, чтоб выполнялось S(0) = 0; для этого должно выполняться C 2 - 2 = 0, т. е. C= 1. Итак, будет нужно 2^n- n- 1 переносов единиц в старшие разряды.
Но формулу 2^n - n - 1 можно вывести, исходя лишь из условия задачки. Обозначим через S(n) исследуемое количество переносов и зацелим, что если прибавлением единиц теснее получено число 2^n-1 - 1 (на это потребуется S(n-l) переносов), то еще одно прибавление единицы востребует n - 1 переносов и приведет к числу 2^n-1, двоичная запись которого есть 10...0 (количество нулей после единицы равно n-1).
Далее в процессе достижения числа 11...1 (n единиц) потребуется еще S(n-l) переносов. Получаем рекуррентное уравнение S(n) = 2S(n - 1) + n - 1 или
S(n)-2S(n-l) = n-l, (1)
при этом s(0) = 0.
Характеристическое уравнение, подходящее рекуррентному уравнению (1), имеет вид А - 2 = 0. Общее решение однородного уравнения S(n) - 2S(n - 1) = 0 есть сТ.
Правую часть уравнения (1) можно записать в виде квазиполинома (n-1)*n. Значение 1 не является корнем характеристического уравнения, поэтому (ур. 1) владеет приватным решением вида an + X; подставляя это выражение вместо s(n) в (1), получаем an + X - 2(а(n - 1) + X) = n - 1, и, приравнивая в левой и правой долях коэффициенты при первой и нулевой ступенях n, имеем а = X = -1. Получаем общее решение уравнения (1): S(n) = C2^n- n- 1. Подбираем значение константы стак, чтоб выполнялось S(0) = 0; для этого должно выполняться C 2 - 2 = 0, т. е. C= 1. Итак, будет нужно 2^n- n- 1 переносов единиц в старшие разряды.
, оставишь ответ?
Похожие вопросы
-
Вопросы ответы
Новое
NEW
Статьи
Информатика
Статьи
Последние вопросы
Предприятие по производству с/хоз продукции на производство затратило 3527000 руб Валовый
Разные вопросы.
Математика, задано на каникулы. ВАРИАНТ 1004
НОМЕР 1,2,3,4,5,6,7,8.
Математика.
Имеются три конденсатора емкостью С1=1мкФ, С2=2мкФ и С3=3мкФ. Какую наименьшую емкость
Физика.
Из точки м выходят 3 луча MP MN и MK причём
Геометрия.
выпиши в свою тетрадь те правила этикета которые тебе не были
Разные вопросы.
Анна хорошо учится у неё много подруг свободное от учёбы время
Обществознание.
10) Килограмм конфет дороже килограмма печенья на 52 р. За 8
Математика.
Во сколько раз число атомов кислорода в земной коре больше числа
Химия.
Составить монолог от имени дневника двоечника 7-10 предложений
Русский язык.
Рассматривая литературный язык как сложное взаимодействие книжного языка и разговорного,В.И.Чернышёв горячо
Разные вопросы.
Облако тегов