Главная страница
    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.037 c
2-1126191575
Чайникп
2005-09-08 18:59
2005.10.16
zip


14-1127384910
ПЛОВ
2005-09-22 14:28
2005.10.16
Вопросик...


3-1125664624
Nickolay
2005-09-02 16:37
2005.10.16
Как в real time из Delphi добавить таблицу в файл mdb?


1-1127845324
Aibolit
2005-09-27 22:22
2005.10.16
вопрос с формами


14-1127337530
Yorick_cool
2005-09-22 01:18
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
Английский Французский Немецкий Итальянский Португальский Русский Испанский