Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

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

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

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

Manufel (2005-09-27 20:55:00) [1]
Ссылка то нерабочая...

TUser (2005-09-26 08:18:00) [2]
Помимо факультета ФИОлогии надо сделать еще факультет ВОЗРАСТоведения и высшую школу ПОЛознания :)

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

jack128 (2005-09-25 23:52:00) [3]
А!!! Так эта ветка еще и в двух экземплярах!!! И обоих обосуждение идет довольно успешно. Конечно до веток об Украинских выборах не еще дотягивает, ну так, как говорится, есть к чему стремиться :-)

SergProger (2005-09-25 23:40:00) [4]
Есть такой вариант:

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

incolex (2005-09-24 22:54:00) [5]
Повторюс ещё разик.
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;

Студент 8) (2005-09-24 22:31:00) [6]
З.З.Ы. Извиняюсь за дублирование сообщений/тем, проблемы с инетом :(((

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

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

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

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

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

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

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

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

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

Virgo_Style (2005-09-24 11:09:00) [10]
Virgo_Style © (24.09.05 11:07) [4]

Хм, кажется, именно это уже предложили в http://www.delphimaster.ru/cgi-bin/forum.pl?id=1127510917&n=0[2] :-)

Virgo_Style (2005-09-24 11:07:00) [11]
Расписывать подробно не буду, но примерчик покажу.

Пусть мы возводим, скажем, с=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 по основанию два (в худшем случае).

GrayFace (2005-09-24 06:43:00) [12]

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

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

Fay (2005-09-24 02:36:00) [13]
Сорри 8)
c := c shl (n - 1) := c shl 6

Fay (2005-09-24 02:35:00) [14]
2 Студент:( (24.09.05 1:28)
>> Если c=2 n=7
c := c shl 7

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »