Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 2005.10.16;
Скачать: [xml.tar.bz2];

Вниз

Вычисление С в степени 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]

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

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

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


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

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

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

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


 
Студент 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;


 
SergProger ©   (2005-09-25 23:40) [11]

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

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


 
jack128 ©   (2005-09-25 23:52) [12]

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


 
TUser ©   (2005-09-26 08:18) [13]

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

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


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

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



Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2005.10.16;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.48 MB
Время: 0.041 c
14-1127729663
Rouse_
2005-09-26 14:14
2005.10.16
SofTool 2005


1-1126457728
Артем Кудлаенко
2005-09-11 20:55
2005.10.16
DCOM. Interface not supported.


2-1127212304
ZSergey
2005-09-20 14:31
2005.10.16
Как получить значение ...


2-1126683639
Dimon777
2005-09-14 11:40
2005.10.16
Как прорисовать Column.Field.DataType=ftBoolean


4-1124123194
dddim
2005-08-15 20:26
2005.10.16
установить Привелегию процессу





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский