может кто подскажет, как посчитать 200!(факториал) за количество шагов не >20????
если за шаг считать одно умножение!!!

Здравствуйте, programmer_kia, Вы писали:

PK>может кто подскажет, как посчитать 200!(факториал) за количество шагов не >20????
PK>если за шаг считать одно умножение!!!
Использовать сложение
А что за задача такая странная?

Здравствуйте, programmer_kia, Вы писали:

PK>может кто подскажет, как посчитать 200!(факториал) за количество шагов не >20????
PK>если за шаг считать одно умножение!!!

По формуле Стирлинга. 1 шаг

Здравствуйте, programmer_kia, Вы писали:

PK>может кто подскажет, как посчитать 200!(факториал) за количество шагов не >20????
PK>если за шаг считать одно умножение!!!

подсказка:
200! = (100!)^2*2^100. последний множитель вычисляется простым сдвигом
100! = (50!)^2*2^50
50! = (25!)^2*2^25
25! = 25*(12!)^2*2^12
12! = (6!)^2*2^6
6! = (3!)^2*2^3
3! = 6
а алгоритм наверно понял

Здравствуйте, ilnar, Вы писали:

i>6! = (3!)^2*2^3

720 = 6! = (3!)^2*2^3 = 6^2 * 8 = 36 * 8 = 288.
720 = 288.

Здравствуйте, programmer_kia, Вы писали:

PK>может кто подскажет, как посчитать 200!(факториал) за количество шагов не >20????
PK>если за шаг считать одно умножение!!!

Предварительно создать таблицу факториалов (скажем до 1000). А потом ЗА ОДИН ШАГ найти 200!

Здравствуйте, ilnar, Вы писали:

I>подсказка:
I>200! = (100!)^2*2^100. последний множитель вычисляется простым сдвигом
I>100! = (50!)^2*2^50
I>50! = (25!)^2*2^25
I>25! = 25*(12!)^2*2^12
I>12! = (6!)^2*2^6
I>6! = (3!)^2*2^3
I>3! = 6
I>а алгоритм наверно понял

Неправда. Взять хотя бы строку:
6! = (3!)^2*2^3

Левая часть:
1*2*3*4*5*6

Правая часть:
1*2*3*1*2*3*2*2*2 = 1*2*3*2*4*6

Итого:
1*2*3*4*5*6 != 1*2*3*2*4*6

А жаль...

Здравствуйте, Михаил Можаев, Вы писали:

ММ>Здравствуйте, ilnar, Вы писали:

I>>подсказка:
I>>200! = (100!)^2*2^100. последний множитель вычисляется простым сдвигом
I>>100! = (50!)^2*2^50
I>>50! = (25!)^2*2^25
I>>25! = 25*(12!)^2*2^12
I>>12! = (6!)^2*2^6
I>>6! = (3!)^2*2^3
I>>3! = 6
I>>а алгоритм наверно понял

ММ>Неправда. Взять хотя бы строку:
ММ>6! = (3!)^2*2^3

ММ>Левая часть:
ММ>1*2*3*4*5*6

ММ>Правая часть:
ММ>1*2*3*1*2*3*2*2*2 = 1*2*3*2*4*6

ММ>Итого:
ММ>1*2*3*4*5*6 != 1*2*3*2*4*6

ММ>А жаль...

лажанулся, ведь даже не подумал об этом,
но факториал можно еще за один шаг вычислить с помощью шаблонов, тогда конечно компилятор будет париться

Здравствуйте, programmer_kia, Вы писали:

PK>может кто подскажет, как посчитать 200!(факториал) за количество шагов не >20????
PK>если за шаг считать одно умножение!!!

Невозможно, по той причине, что на отрезке [1, 200] больше 20 простых чисел (и каждое из них присутствует в разложении числа 200! хотя бы в степени 1).

Здравствуйте, programmer_kia, Вы писали:

PK>может кто подскажет, как посчитать 200!(факториал) за количество шагов не >20????
PK>если за шаг считать одно умножение!!!

200! = 2^197 * 3^97 * 5^49 * 7^32 * 11^19 * 13^16 * 17^11 * 19^10 * 23^8 * 29^6 * 31^6 * 37^5 * 41^4 * 43^4 * 47^4 * 53^3 * 59^3 * 61^3 * 67^2 * 71^2 * 73^2 * 79^2 * 83^2 * 89^2 * 97^2 * 101 * 103 * 107 * 109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167 * 173 * 179 * 181 * 191 * 193 * 197 * 199

Нельзя умножить менее, чем за 20 шагов.

Разложение факториала числа в такой вид можно сделать по следующему скрипту (для MatLab):

N = 200;
p = primes(N); % находим все простые числа до N
s = zeros(1,length(p));
for i=2:N,   
    primes_factor = factor(i); % раскладываем на простые множители
    for j=1:length(primes_factor),
        indx = find(p==primes_factor(j));
        s(indx) = s(indx) + 1;
    end
end
% выводим результат
fprintf(['%d! = '],N);
for i=1:length(p),   
    if s(i)~=0,
        if i~=1,
            fprintf([' * ']);
        end
        if s(i)>1,
            fprintf([' %d^%d'],p(i),s(i));
        else
            fprintf([' %d'],p(i));            
        end
    end
end

Примеры вычислений:
10! = 2^8 * 3^4 * 5^2 * 7
20! = 2^18 * 3^8 * 5^4 * 7^2 * 11 * 13 * 17 * 19
30! = 2^26 * 3^14 * 5^7 * 7^4 * 11^2 * 13^2 * 17 * 19 * 23 * 29
100! = 2^97 * 3^48 * 5^24 * 7^16 * 11^9 * 13^7 * 17^5 * 19^5 * 23^4 * 29^3 * 31^3 * 37^2 * 41^2 * 43^2 * 47^2 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97

Здравствуйте, programmer_kia, Вы писали:

PK>может кто подскажет, как посчитать 200!(факториал) за количество шагов не >20????
PK>если за шаг считать одно умножение!!!

Забей таблицу констант!

Здравствуйте, vvaizh, Вы писали:

V>Забей таблицу констант!

А лучше просто забей

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, programmer_kia, Вы писали:

PK>>может кто подскажет, как посчитать 200!(факториал) за количество шагов не >20????
PK>>если за шаг считать одно умножение!!!

К>Невозможно, по той причине, что на отрезке [1, 200] больше 20 простых чисел (и каждое из них присутствует в разложении числа 200! хотя бы в степени 1).

ИМХО, условие задачи сформулировано несколько расплывчато.

если условие задачи уточнить — не использовать изначально числа > 200, то

200! = X ^ N + Y

с учётом того, что 200! ~= 10^375
200! ~= 200^162

X = 200
N = 162, и 200^162 вычисляется за 7 умножений (и 2 сложения)
Оставшиеся 12 умножений с лихвой хватит на вычисление остатка Y = 200! — 200^162

Здравствуйте, TomRay, Вы писали:

TR>Предварительно создать таблицу факториалов (скажем до 1000). А потом ЗА ОДИН ШАГ найти 200!

Кто в .NET работает? Там нет таблиц всяких (факториалы, простые числа ...)?

Здравствуйте, FireShock, Вы писали:

FS>Кто в .NET работает? Там нет таблиц всяких (факториалы, простые числа ...)?

Факториалы

13! = 6'227'020'800 > 2^32 = 4'294'967'296

А таблицу из 12 чисел заполнить от руки легко (а то и вычислять на ходу).