Сколько всего будет вариантов?

Question

[haqz]

есть число=200

Из него надо вычесть 150 раз(сделать 150 "шагов") по 1 и 2 следующим образом:

n - это случайное число от 1 до 149.

r1,r11 .... r149,r149149 это результаты
шаг 1;

r1 = 150- 1-n, r11= 150-2-n

Шаг 2:

Берем результаты из шагам и еще раз вычитаем 1 и 2:

r2= r1 - 1 - n

r22 = r11 - 1 - n

Шаг 3:

Берем все прошлые результаты и из них еще раз вычитаем по 1 и по 2 с n, и так все 149 шагов

Сколько всего будет(точно или приблизительно) результатов ?

Спасибо

УТОЧНЕНИЕ К ВОПРОСУ:

Дано X,

Производится операция:

i принимает значения 1 и 4

N = 10...1

N на этом шаге = 10:

Xшаг1,1= X-i1 - i* N
Xшаг2,2 = Xi4 - i*N

Следующий шаг:

N = 9

Yiшаг2,1 = Xi1 - i* 9

Yiшаг2,2 = Xi4 - i*9

Yшаг2,3 = Xшаг1,1 - i*9

Yшаг2,4 = Xшаг2,2 - i*9

Следующий шаг

N = 8

делаю Z,1 = Xi1- i*8

Z1,4 = Xi4 - i*8

...

и теперь далее по этому шагу со всеми прошлыми пезультатами тоже самое делается

т.е из

Xшаг1,1;Xшаг1,2;Yiшаг2,1,Yiшаг2,3

опять вычитаю i и потом вычитаю i * 8.

Сколбко всего будет вариантов чтобы расчитать для N = 20 т.е для 20 шагов ?

Большое спасибо. Прошу любые гипотезы. Правильно я понимаю, что вариаетов будет меньше чем 2^20 или всетаки 2^20 ?

Большое спасибо

Comments

[Wataru]

Непонятно. Случайное число берем один раз и фиксируем, или оно разное на каждом шаге?
Результаты нужны только уникальные? Так-то на каждом шаге вычиаем и 1 и 2, так что количество результатов увеличивается в 2 раза и будет что-то порядка 2^150 результатов в конце. Можно ли вычитать в отрицательные числа?

[Lynn «Кофеман»]

В отрицательную область можно заходить?

Вообще выглядит как что-то похожее на фибоначчи

[haqz]

@wataru

В отрицательную не уходит,заменил в описании случайную на от 20 до 1. Т.е шагов всего 20 шт

2^20 варианиов будет или меньше ?

Спасибо

[Wataru]

haqz, Понятнее не стало. У вас какие-то иксы, игреки, зеды. Двойные/тройные индексы, от балды меняющиеся. Где-то i в индексах проскакивает, где-то нет. Полная мешанина, короче.

Уменьшите задачу еще. Пусть изначальне число 10. Делаем ровно 2 шага. На каждом шаге можно вычитать 1 и 2. Вот распишите все числа на каждом шаге. значениями числовыми и как они вычислялись.
Формулы со * оборачивайте в тег code (кнопка </> в редакторе), а то похоже часть их съедается парсером.

[CBET_TbMbI]

Я вообще ничего не понял, кроме первых 2 строчек. На редкость запутанная формулировка.
Есть 200. Надо из неё вычитать единицы и двойки 150 раз.

Если в отрицательные уйти не может, то остаться может 51 вариант: от 0 до 50 включительно.

Что такое n, r149149 вообще без понятия

Answer 1

[Griboks]

У вас неправильно написан алгоритм. Либо "Берем все прошлые результаты и из них еще раз вычитаем по 1 и по 2", либо "r2= r1 - 1 - n, r22 = r11 - 1 - n".

Comments

[haqz]

Griboks, а при алгоритме как вы написали, сколько вариантов получится ?

Спасибо

[Griboks]

haqz, если вы на каждом шаге вычисляете r[1,i+1]=r[2,i]-1-n и r[2,i+1]=r[2,i]-2-n, то всего получится 2*150=300 результатов, из которых на последнем шаге будет ровно два.

[haqz]

Griboks, На каждом новом шаге еше от предыдущих результатрв по 2 считается .

Что в итоге получится ?

Большое Спасибо

[Griboks]

haqz, тогда это будет геометрическая прогрессия, и вам нужен её член под номером 150, который равен 2^150=1.42724769270596e+45.