Вычисление С в степени N с минимальным количеством умножений

← →
Студент:( (2005-09-24 01:28) [0]

Господа програмисты, помогите плиз
Срочно необходимо такую вещь в универ:
реализовать программу в которую вводится целых числа C и N
необходимо вычислить С в степени N используя минимальное число операций умножения
Если не совсем ясно высказался:
Если c=2 n=7
то лучшее это
c:=c*c;
c:=c*c;
c:=c*c;
c:=c/2;

(естесно не в таком виде, с if, for и самым простым я знаком)

Очень прошу помочь, желательно напишите готовый код в виде консольного приложения, а то я разбираюсь плохо... а сделать надо

← →
Fay © (2005-09-24 02:35) [1]

2 Студент:( (24.09.05 1:28)
>> Если c=2 n=7
c := c shl 7

← →
Fay © (2005-09-24 02:36) [2]

Сорри 8)
c := c shl (n - 1) := c shl 6

← →
GrayFace © (2005-09-24 06:43) [3]

> c := c shl (n - 1) := c shl 6

3^2=6? Не знал...

← →
Virgo_Style © (2005-09-24 11:07) [4]

Расписывать подробно не буду, но примерчик покажу.

Пусть мы возводим, скажем, с=5 в n=7-ю степень.

5^7 = 5*5*5*5*5*5*5*5; // 7 умножений.

Но. после первого же умножения мы получим 5^2. А из него одним (!) умножением можем получить 5^4. И тогда можно сократить количество умножений:

5^2 = 5*5; 5^4 = (5^2)*(5^2); 5^7 = (5^4)*(5^2)*5; // в сумме 4 умножения!

А если нужна девятая степень?

5^2 = 5*5; 5^4 = (5^2)*(5^2); 5^8 = (5^4)*(5^4); 5^9 = (5^8)*5; // опять 4 умножения, но уже вместо 9-ти.

Какие степени c^2k нам нужно перемножить для получения результата, покажет двоичная запись n:
n=7: 1 1 1 степени 4 2 1
перемножаем (c^4)*(c^2)*c;

n=9: 1 0 0 1 степени 8 4 2 1
перемножаем (c^8)*c;

И так далее. Насколько я помню, число операций пропорционально логарифму c по основанию два (в худшем случае).

← →
Virgo_Style © (2005-09-24 11:09) [5]

Virgo_Style © (24.09.05 11:07) [4]

Хм, кажется, именно это уже предложили в http://delphimaster.net/view/1-1127510917/ [2] :-)

← →
Студент 8) (2005-09-24 22:24) [6]

Спасибо огромное всем кто потратил время, а отдельно Lamer@fools.ua и Virgo_Style
Разобрался, сделал =) Вы мне очень помогли, задачку мне дал препод на факультете ФИОЛОГИИ(!!!) по ПРОГРАМИРОВАНИЮ НА ЭВМ(Это у нас то на факультете!!!), зачем оно(програмирование) нам нужно никто даже предположить не может, но препод почемуто считает нас сильно продвинутыми математиками-програмистами и даёт задачи которые самостоятельно почти никто не может...

В общем всем спасибо!

З.Ы. Просьба не писать какие студенты глупые пошли, и не могут простую задачу решить, не забывайте, что это не математический факультет...

← →
Студент 8) (2005-09-24 22:24) [7]

← →
Студент 8) (2005-09-24 22:26) [8]

← →
Студент 8) (2005-09-24 22:31) [9]

З.З.Ы. Извиняюсь за дублирование сообщений/тем, проблемы с инетом :(((

← →
incolex © (2005-09-24 22:54) [10]

Повторюс ещё разик.
IntPower (X: Extended; Y: Integer ): Extended; - эта ф-ция возводит число только в цлочисленную степень.
Power ( X, Y: Extended ): Extended; - возводит в дробную степень.

Пример:
var
z1, z2: Real;
begin
...
z1:= IntPower(0.5, -2); {z1:=4}
z2:= IntPower(0.5, 2); {z2:=0.25}
...
end;

Есть такой вариант:

C:=Exp(n*Ln(C));

А!!! Так эта ветка еще и в двух экземплярах!!! И обоих обосуждение идет довольно успешно. Конечно до веток об Украинских выборах не еще дотягивает, ну так, как говорится, есть к чему стремиться :-)

Помимо факультета ФИОлогии надо сделать еще факультет ВОЗРАСТоведения и высшую школу ПОЛознания :)

Вот - скачал когда-то с сайта blackman"а. Сейчас эта книга естьи в бумажном виде
http://monkey.belozersky.msu.su/~evgeniy/THEOR.htm

← →
Manufel (2005-09-27 20:55) [14]

Ссылка то нерабочая...

Вычисление С в степени N с минимальным количеством умножений Найти похожие ветки