Lec_07

Пример

35

1.i = (индекс старшего коэффициента A) = 4

a)Угадываем q[0] = 1

b)Вычитаем сдвинутое B*1 = 513 из A (на бумаге мы при этом пишем только значимую для следующего шага часть A)

2.i = 3

a)Угадываем q[1] = 3

b)Вычитаем сдвинутое B*3 = 1539 из A

3.i = 2

a)Угадываем q[3] = 4

b)Вычитаем сдвинутое B*4 = 2052 из A

4.i < m = 2, процесс закончен.

То, что осталось от A после вычитаний является остатком деления.

Пример. продолжение

36

Довольно интересный способ состоит в высказывании догадки q по первым цифрам делителя и делимого.

Понятно, что этих нескольких цифр недостаточно для гарантированно правильного результата, однако неплохое приближение все же получится.

Пусть очередной шаг представляет собой деление некоторого

U = (u0, u1, …, un) на B=(b0, b1, …, bn-1).

Если bn-1 ≥ BASE/2, то можно доказать следующие факты.

1.Если положить qGuess = (un*BASE + un-1) / bn-1 , то qGuess-2

≤ q ≤ qGuess.

2.Если же дополнительно выполняется неравенство qGuess*bn-2 > BASE*r + un-2 ,

где r – остаток при нахождении qGuess и qGuess ≠ BASE,

то qGuess-1 ≤ q ≤ qGuess,

причем вероятность события qGuess = q+1 приблизительно равна 2/BASE.

Пример. продолжение

37

Таким образом, если bn-1 ≥ BASE/2,

то можно вычислить qGuess = (un*BASE + un-1) / bn-1 и уменьшать на единицу до тех пор, пока не станут выполняться условия (2).

Получившееся значение будет либо правильным частным q, либо, с вероятностью 2/BASE, на единицу большим числом.

Если bn-1 слишком мало,

то можно, например, умножить делитель и делимое на одно и то же число scale = BASE / ( bn-1 +1 ).

При этом несколько изменится способ вычисления остатка, а частное останется прежним.

Такое умножение иногда называют нормализацией числа.

Задачи…

38

7.1) напишите программу вычисления точного значения n!, где n>12.

Код задачи 7.1

void MulLong(int a[],int b,int c[]) { int i;

for (i=1;i<=c[0];i++) c[i]=0; for (i=1;i<=a[0];i++) {

c[i+1]=(c[i]+(long)a[i]*b)/osn;

c[i]=(c[i]+(long)a[i]*b)%osn;

}

if (c[a[0]+1]>0) c[0]=a[0]+1; else c[0]=a[0]; while (c[c[0]]>=osn) {

c[c[0]+1]=c[c[0]]/osn;

c[c[0]]=c[c[0]]%osn;

c[0]++;

}

if (b>1) {

b--; MulLong(c,b,a);

}

return;

}

задачаФЛАГИ

7.2) Флаг состоит из n вертикальных полос белого, красного и синего цвета. Соседние полосы не могут иметь одинаковый цвет, а синяя полоса всегда должна находиться между красной и белой. Сколькими способами можно покрасить флаг из n полос?

Анализ задачи 7.2

Обозначим через fred(n) и fwhite(n) количество способов раскраски флага из n полос при условии, что первой полосой будет соответственно

красная или белая.

Тогда

fred(1) = 1,	fred(2) = 1,	fred(n) = fwhite(n – 1)	+ fwhite(n – 2);
fwhite(1) = 1,	fwhite(2) = 1,	fwhite(n) = fred(n – 1)	+ fred(n – 2).

Если f(n) – искомое общее количество способов раскраски,

то f(n) = fred(n) + fwhite(n)

Поскольку

fred(1) = fwhite(1) = 1,

fred(2) = fwhite(2) = 1,

а fred(n) и fwhite(n) одними формулами выражаются друг через друга,

то fred(n) = fwhite(n) = fn, где fn – n-ое число Фибоначчи.

Таким образом f(n) = 2 * fn

Решение задачи 7.2

Для N<=45

__int64 fib[46];

Читаем входное значение n. Нахождение значения fib[n] совершим в цикле:

scanf("%d",&n); fib[1] = 1; fib[2] = 1;

for(i=3;i<=n;i++) fib[i] = fib[i-1] + fib[i-2];

Выводим результат f(n) = 2* fred(n) = 2 * fib[n]:

printf("%I64d\n",2*fib[n]);

Задачи…

43

7.3) Вывести на экран 2^n,

где n<=10000, n – натуральное

Решение задачи 7.3

		var A: array[1 .. 3750] of word;		Nach: word;	i,N,j: word;
		begin
		for i:=2 to 3750 do A[i]:=0;
		A[1]:=1;	{ 2^0=1 }
		read(N);	{ получаем степень}
		Nach:=2;	{ индекс первой ячейки массива A }

for i:=1 to N do begin

Perenos:=0; { перенос в след элем. массива A } for j:=1 to Nach+1 do begin

A[i]:=A[i]+A[i]+Perenos; { складываем 4 текущ. Разряда + добавляем перенос из предыд. 4 разрядов}

if A[i]>=10000	then begin		{ если в числе больше 4 цифр }
Perenos:=A[i] div		10000;	{ формируем перенос}
A[i]:=A[i] mod		10000;	{ оставляем в числе 4	посл цифры}
end else Perenos:=0			{ если переноса нет }

end;

if A[Nach+1]>0 then Nach:=Nach+1;

{ если перенос в не использованную ячейку массива А то увеличим индекс} end;