Помогите с задачей, плз

← →
ProgRAMmer Dimonych © (2006-10-13 23:17) [0]

В последовательности чисел a1, a2, ... каждый элемент, начиная с четвёртого, равен последней цифре суммы трёх предыдущих. Написать программу, которая по заданным a1, a2, a3 и N определяет aN (N<=1000000000). Алгоритм с количеством действий, пропорциональным N недопустим.

А то я чё-то уже торможу :( Яндекс ничего толкового не выдал: 5 ссылок на страницы с условием и одну на форум, где есть эта задача (без ограничения на кол-во действий) и решение (на Бейсике, что не так уж и важно, и написанное без тени мысли, IMHO, что уже страшно). Закономерность я не обнаружил. Одно радует, что достаточно знать только последние цифры чисел. Но получать все числа нельзя (кол-во действий).

Заранее огромное спс...

← →
wl © (2006-10-13 23:27) [1]

попробуй на листочке бумаги посчитать a[i] до 10 включительно, если алгоритм не вырисуется, тогда и будем думать.
а то щаз начнут пугать словами, типа "Динамическое программирование" или ещё хуже

← →
Чапаев © (2006-10-13 23:30) [2]

> [1] wl © (13.10.06 23:27)

на 6 вроде начал вырисовываться, на семёрке всё сбилось. %-) Думал, треугольник Паскаля как-то сюда отнести -- пока не удаётся...

← →
ProgRAMmer Dimonych © (2006-10-13 23:35) [3]

На листочке я для первых 1, 2, 3 штук 30 чисел набрал - ничего.

← →
ferr © (2006-10-13 23:37) [4]

> треугольник Паскаля как-то сюда отнести

у него природа другая) тут mod 10, это многое портит.. или облегчает, единственный путь который пока вижу -- это искать периоды))

← →
Чапаев © (2006-10-13 23:38) [5]

> [3] ProgRAMmer Dimonych © (13.10.06 23:35)

Числа тут не помогут. Формулу искать надо.

← →
ProgRAMmer Dimonych © (2006-10-13 23:40) [6]

Так вот, как уже было сказано, mod всё портит. Его ведь и дробь по-человечески не заменить :(

← →
Чапаев © (2006-10-13 23:43) [7]

Есть такая теорема, что (А+B) mod k==(A mod k)+(B mod k).
То же для "-" и "*". Даже специальная система счисления есть -- система остаточных кодов.

← →
ProgRAMmer Dimonych © (2006-10-13 23:46) [8]

ОК, тогда четвёртое число равно (a+b+c)/10 (/ - mod). Пятое - (a+b+c)/10+(b+c)/10. Кажется, так... Не нарисовывается... :(

← →
Чапаев © (2006-10-13 23:47) [9]

> [8] ProgRAMmer Dimonych © (13.10.06 23:46)

А дальше оно ещё неприятнее "не нарисовывается"... ;-)

← →
ferr © (2006-10-13 23:50) [10]

> Есть такая теорема, что (А+B) mod k==(A mod k)+(B mod k)
> .
> То же для "-" и "*". Даже специальная система счисления
> есть -- система остаточных кодов.

(7 + 7) mod 9 != (7 mod 9) + (7 mod 9) ? mod"a не хватает

Мне казалось что это называется кольцом классов вычетов..

← →
Чапаев © (2006-10-13 23:50) [11]

вообще, кажется, можно an представить как x*(a+b+c)+y*(b+c)+z*c, а x, y, z уже будут подчиняться каким-то более-менее несложным законам.

← →
ferr © (2006-10-13 23:58) [12]

чтот не охото математическое решение искать)) можно вот об этом сказать "Алгоритм с количеством действий, пропорциональным N недопустим."?

← →
ProgRAMmer Dimonych © (2006-10-14 00:07) [13]

Вот помучил (/ равносильно mod):

a -> b -> c -> (a+b+c)/10 -> (a+11b+11c)/100 -> (11a+21b+121c)/1000 -> (121a+231b+331c)/10000...

Нет закономерности :), наверное...

← →
Чапаев © (2006-10-14 00:09) [14]

Можно сделать алгоритм с количеством действий, пропорциональным N*N. Имхо условия задачи не нарушит. ;-)

← →
ProgRAMmer Dimonych © (2006-10-14 00:09) [15]

Ой, наврал... mod - это ж не div, делением заменять нельзя...

← →
ProgRAMmer Dimonych © (2006-10-14 00:10) [16]

> [14]
Такое я и сам могу, а при большом желании и в N*N*N*N*N*N*N*N*N смогу уложиться :)

← →
ProgRAMmer Dimonych © (2006-10-14 00:36) [17]

Неужели никто не встречался с такой задачей?

← →
default © (2006-10-14 01:10) [18]

представьте ряд цифр убегающий в бесконечность
и мыслите его непересекающимися тройками цифр
всего комбинаций из трёх цифр 10*10*10=1000, то есть это конечное число и значит какая-то комбинация из трёх цифр повторится рано или поздно и цикл замкнётся, то есть будет периодика
как отловить период? да проще пареной репы...
держим массив всех комбинаций троек цифр - всего 1000 элементов будет в нём и фиксируем с помощью него какие тройки цифр уже встретились
как только зафиксировали повторение, дело сделано, период схвачен
если этих пояснений не хватает светлым умам я умываю руки

← →
ProgRAMmer Dimonych © (2006-10-14 10:01) [19]

Это понятно, только для решения задачи нужно знать, когда начнётся зацикливание и какой длины будет период. И ещё не факт, что для любой тройки эти параметры будут одинаковыми :(

← →
palva © (2006-10-14 10:12) [20]

Ну вот и надо написать программу, которая схватит этот период.

← →
ProgRAMmer Dimonych © (2006-10-14 11:01) [21]

А уверенность в том, что для любых трёх первых чисел период будет одинаковым?

← →
MeF Dei Corvi © (2006-10-14 12:11) [22]

> А уверенность в том, что для любых трёх первых чисел период
> будет одинаковым?

Нет такой уверенности. А зачем она? Просто считаем последовательности из трех цифр. Сравниваем с первыми(которые были введены). Как только они равны - мы нашли период. Далее можно либо посчитать N, либо сразу вывести его, если запоминать всю периодическую последовательность в массив.

← →
MeF Dei Corvi © (2006-10-14 12:19) [23]

> Просто считаем последовательности из трех цифр. Сравниваем
> с первыми(которые были введены).

Считаем последовательность из трех Ai. Сравниваем с первыми посчитанными Ai.

← →
default © (2006-10-14 13:17) [24]

он так ничего и не понял...

← →
default © (2006-10-14 13:48) [25]

когда я говорил о массиве из 1000 элементов я имел ввиду массив
a: Array[0.999] of Boolean; каждый элемент которого изначально установлен в False
посчитали три цифры: d1,d2,d3 и выставляем a[d1*100+d2*10+d3] в True если там стояло False, если там True то значит нашли повторение
могут быть модификации этой схемы или другие схемы, но это всё уже детали реализации, идея была дана
а реализует пусть сам автор сабжа иначе пользы от задачи будет 0
p.s. всё меня нет

← →
Alx2 © (2006-10-14 14:33) [26]

Святотатствуя, даю маячок: :)
#include <iostream.h> class CTriple { private: int a0,a1,a2; public: CTriple(int s0, int s1, int s2){a0=s0;a1=s1;a2=s2;}; CTriple(){}; CTriple& operator ++(int) { int t2=a2; a2 = (a0+a1+a2)%10; a0 = a1; a1 = t2; return *this; } bool operator !=(CTriple &V){return a0!=V.a0||a1!=V.a1||a2!=V.a2;} friend ostream& operator<<(ostream &s, CTriple &V) { return s<<V.a0; } }; typedef unsigned int UINT; template <class type> class CSequence { private: type Init; UINT Period; UINT NPPLength; void SetSequenceParameters() { type T=Init; type Start=T; Period=1; while (Start++!=T++++) Period++; NPPLength=0; T=Init; while (T!=Start) { NPPLength++; T++; Start++; } } public: CSequence(type &aInit) { Init=aInit; SetSequenceParameters(); } type operator [](UINT N) { UINT Counter; if (N>NPPLength) Counter=NPPLength; else Counter=N; N-=Counter; type T=Init; for (UINT k=0;k<Counter;k++) T++; if (N>=Period) N%=Period; for (k=0;k<N;k++) T++; return T; } }; void main() { // Нумерация с нуля :) cout<<CSequence<CTriple>(CTriple(1527,443,2215))[1000000000-1]; }

← →
ProgRAMmer Dimonych © (2006-10-14 14:46) [27]

Спасибо всем!!!

Отдельно default"у. Я бы, наверное, дня два (говорю совершенно серьёзно) в своём тормозном состоянии ещё думал, как искать повторы этих троек. Ещё раз почувствовал гордость за братьев славян.

← →
MeF Dei Corvi © (2006-10-14 16:06) [28]

> Святотатствуя, даю маячок: :)

Фига се маячок) Это ж пару часов разбираться в том, что конкретно в ней происходит)

>MeF Dei Corvi © (14.10.06 16:06)

>Это ж пару часов разбираться в том, что конкретно в ней происходит)

А комментарии нарочно не писал. :)

В SetSequenceParameters считается период и длина непериодической стартовой части последовательности. Период считается прогоном по последовательности двух ее элементов. Первый идет с шагом 1. Второй с шагом 2. Когда они совпадают, то расстояние между ними будет кратно периоду.

Получать в точности период по условиям задачи не обязательно, хотя и не трудно - достаточно повторить вышеописанный прогон еще раз, начиная с элемента, который остался после того прогона.

Потом считается длина непериодической части - смотрим с какого момента (с какого "k") начинает выполянтся равенство f(k)=f(k+Period).

Если знаем длину непериодической части последовательности и ее период, то все остальное совсем просто.

МВо как-то давал решение за О(1). Поиск по ключевым словам "ряд триббоначи" - а дальше там есть радикальная формула, позволяющая вычислять N-ый член ряда (как и для Фиббоначи).

И еще на форуме проскакивала ссылка на базу данных по последовательностям чисел. Туда ввести первые числа твоей последовательности - и найдешь формулу.

>TUser © (14.10.06 16:37)

Линк на базу: http://www.research.att.com/~njas/sequences/index.html

>МВо как-то давал решение за О(1).
Дам сейчас ту радикальную формулу. Считается, действительно, за O(ln(n)) где n - номер элемента. В степень ведь возводить надо?

А вот формула (кроме шуток):
f(n) =
1/528*(-1584*a1*(19+3*sqrt(33))^(1/3)-594*a2*(19+3*sqrt(33))^(2/3)+312*sqrt(33)*a0-66*(19+3*sqrt(33))^(2/3)*a0+528*(19+3*sqrt(33))^(1/3)*a0-108*(19+3*sqrt(33))^(2/3)*sqrt(33)*a1+114*a2*(19+3*sqrt(33))^(2/3)*sqrt(33)-78*(19+3*sqrt(33))^(2/3)*sqrt(33)*a0-264*a0-2376*a2+1584*a1-456*a2*sqrt(33)+432*sqrt(33)*a1+132*I*sqrt(3)*a1*(19+3*sqrt(33))^(2/3)-104*I*sqrt(3)*sqrt(33)*a0+152*I*a2*sqrt(3)*sqrt(33)-144*I*sqrt(3)*sqrt(33)*a1-528*I*sqrt(3)*a1*(19+3*sqrt(33))^(1/3)-198*I*sqrt(3)*a2*(19+3*sqrt(33))^(2/3)+330*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*a0+396*a1*(19+3*sqrt(33))^(2/3)+792*I*a2*sqrt(3)+18*I*sqrt(3)*(19+3*sqrt(33))^(4/3)*sqrt(33)*a1-1320*I*sqrt(3)*a0-528*I*sqrt(3)*a1-36*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*sqrt(33)*a1-26*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*sqrt(33)*a0+176*I*sqrt(3)*(19+3*sqrt(33))^(1/3)*a0+99*I*sqrt(3)*a2*(19+3*sqrt(33))^(4/3)-77*I*sqrt(3)*(19+3*sqrt(33))^(4/3)*a0-66*I*sqrt(3)*a1*(19+3*sqrt(33))^(4/3)+38*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*sqrt(33)*a2+13*I*sqrt(3)*(19+3*sqrt(33))^(4/3)*sqrt(33)*a0-19*I*sqrt(3)*(19+3*sqrt(33))^(4/3)*sqrt(33)*a2)*(1/3*(19+3*sqrt(33))^(1/3)+4/3/((19+3*sqrt(33))^(1/3))+1/3)^n/(-3*(19+3*sqrt(33))^(2/3)-4*I*sqrt(3)-12+I*sqrt(3)*(19+3*sqrt(33))^(2/3))+1/132*(132*I*sqrt(3)*a0-132*(19+3*sqrt(33))^(2/3)*a0-132*(19+3*sqrt(33))^(1/3)*a0+396*a1*(19+3*sqrt(33))^(1/3)-528*a0+264*I*sqrt(3)*a1-66*I*(19+3*sqrt(33))^(2/3)*sqrt(3)*a1-33*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*a0+99*I*a2*(19+3*sqrt(33))^(2/3)*sqrt(3)-396*I*a2*sqrt(3)+4*I*sqrt(3)*sqrt(33)*(19+3*sqrt(33))^(1/3)*a0+18*I*(19+3*sqrt(33))^(2/3)*sqrt(3)*sqrt(33)*a1-19*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*sqrt(33)*a2-76*I*a2*sqrt(3)*sqrt(33)+36*I*sqrt(3)*sqrt(33)*a1*(19+3*sqrt(33))^(1/3)+72*I*sqrt(3)*sqrt(33)*a1-16*I*a2*(19+3*sqrt(33))^(1/3)*sqrt(3)*sqrt(33)+52*I*sqrt(3)*sqrt(33)*a0+13*I*sqrt(3)*sqrt(33)*(19+3*sqrt(33))^(2/3)*a0)*(-1/6*(19+3*sqrt(33))^(1/3)-2/3*1/((19+3*sqrt(33))^(1/3))+1/3+1/2*I*sqrt(3)*(1/3*(19+3*sqrt(33))^(1/3)-4/3*1/((19+3*sqrt(33))^(1/3))))^n/(-3*(19+3*sqrt(33))^(2/3)-4*I*sqrt(3)-12+I*sqrt(3)*(19+3*sqrt(33))^(2/3))+(7/192*(19+3*sqrt(33))^(2/3)*a0+1/48*(19+3*sqrt(33))^(1/3)*a0-3/352*(19+3*sqrt(33))^(2/3)*sqrt(33)*a1-1/16*a1*(19+3*sqrt(33))^(1/3)-3/64*a2*(19+3*sqrt(33))^(2/3)+19/2112*a2*(19+3*sqrt(33))^(2/3)*sqrt(33)+1/528*(19+3*sqrt(33))^(1/3)*a0*sqrt(33)-13/2112*(19+3*sqrt(33))^(2/3)*sqrt(33)*a0-1/132*a2*(19+3*sqrt(33))^(1/3)*sqrt(33)+3/176*sqrt(33)*a1*(19+3*sqrt(33))^(1/3)+1/3*a0+1/32*a1*(19+3*sqrt(33))^(2/3)+3/352*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*sqrt(33)*a1+13/2112*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*sqrt(33)*a0-1/32*I*sqrt(3)*a1*(19+3*sqrt(33))^(2/3)-1/16*I*sqrt(3)*a1*(19+3*sqrt(33))^(1/3)+3/64*I*sqrt(3)*a2*(19+3*sqrt(33))^(2/3)-7/192*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*a0+1/48*I*sqrt(3)*(19+3*sqrt(33))^(1/3)*a0-1/132*I*sqrt(3)*(19+3*sqrt(33))^(1/3)*sqrt(33)*a2+1/528*I*sqrt(3)*(19+3*sqrt(33))^(1/3)*sqrt(33)*a0+3/176*I*sqrt(3)*(19+3*sqrt(33))^(1/3)*sqrt(33)*a1-19/2112*I*sqrt(3)*(19+3*sqrt(33))^(2/3)*sqrt(33)*a2)*(-1/6*(19+3*sqrt(33))^(1/3)-2/3*1/((19+3*sqrt(33))^(1/3))+1/3-1/2*I*sqrt(3)*(1/3*(19+3*sqrt(33))^(1/3)-4/3*1/((19+3*sqrt(33))^(1/3))))^n

Сорри. Не расставил переносы. Запорол ветку :(

Есть и проще,
http://mathworld.wolfram.com/TribonacciNumber.html

Можно также возводить в степень матрицу 3х3, там будет логарифмическая оценка времени.

>TUser © (14.10.06 16:48) [34]
>Есть и проще

Не проще. Там where alpha,betamgamma are the three roots of the polynomial...

То, что я написал - как раз эти кабанские корни кубического уравнения

>Можно также возводить в степень матрицу 3х3, там будет
>логарифмическая оценка времени.

А вот за это - спасибо. Я в очередной раз забыл о простых методах :)

>TUser © (14.10.06 16:48) [34]

Но в приведенном коде сложность все-таки меньше: O(T)= O(1) где T - период.

А модульная арифметика здесь дает логарифмическую сложность и для явной формулы.

>ProgRAMmer Dimonych
для меня лично задача крайне сложная, можно узнать, почему она возникла? олимпиада какая-то или ?

> олимпиада какая-то или ?

Для олимпиады ИМХО слишком простая.

кстати, вот ещё вам до кучи способ определения периода(правда не обязательно минимального, то есть возможно кратного минимальному)
комбинаций из трёх цифр, как уже говорилось, 1000
то есть в 1001 тройке цифр хотя бы две тройки цифр одинаковые
стало быть период, как минимум, начнётся с 1001 тройки, стало быть эта тысячная тройка заведомо часть периода
так вот идея в том чтобы заранее посчитать и хранить эту 1001 тройку
а в программе искать тройку с ней совпадающую с начала последовательности, обнаружили совпадение - получили период:)
никакой памяти дополнительной тут не требуется и программа упрощается заметно

Помогите с задачей, плз Найти похожие ветки