Форум: "Прочее";
Текущий архив: 2006.11.05;
Скачать: [xml.tar.bz2];
ВнизПомогите с задачей, плз Найти похожие ветки
← →
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]
> Святотатствуя, даю маячок: :)
Фига се маячок) Это ж пару часов разбираться в том, что конкретно в ней происходит)
← →
Alx2 © (2006-10-14 16:20) [29]>MeF Dei Corvi © (14.10.06 16:06)
>Это ж пару часов разбираться в том, что конкретно в ней происходит)
А комментарии нарочно не писал. :)
В SetSequenceParameters считается период и длина непериодической стартовой части последовательности. Период считается прогоном по последовательности двух ее элементов. Первый идет с шагом 1. Второй с шагом 2. Когда они совпадают, то расстояние между ними будет кратно периоду.
Получать в точности период по условиям задачи не обязательно, хотя и не трудно - достаточно повторить вышеописанный прогон еще раз, начиная с элемента, который остался после того прогона.
Потом считается длина непериодической части - смотрим с какого момента (с какого "k") начинает выполянтся равенство f(k)=f(k+Period).
Если знаем длину непериодической части последовательности и ее период, то все остальное совсем просто.
← →
TUser © (2006-10-14 16:37) [30]МВо как-то давал решение за О(1). Поиск по ключевым словам "ряд триббоначи" - а дальше там есть радикальная формула, позволяющая вычислять N-ый член ряда (как и для Фиббоначи).
← →
TUser © (2006-10-14 16:39) [31]И еще на форуме проскакивала ссылка на базу данных по последовательностям чисел. Туда ввести первые числа твоей последовательности - и найдешь формулу.
← →
Alx2 © (2006-10-14 16:42) [32]>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
← →
Alx2 © (2006-10-14 16:43) [33]Сорри. Не расставил переносы. Запорол ветку :(
← →
TUser © (2006-10-14 16:48) [34]Есть и проще,
http://mathworld.wolfram.com/TribonacciNumber.html
Можно также возводить в степень матрицу 3х3, там будет логарифмическая оценка времени.
← →
Alx2 © (2006-10-14 16:52) [35]>TUser © (14.10.06 16:48) [34]
>Есть и проще
Не проще. Там where alpha,betamgamma are the three roots of the polynomial...
То, что я написал - как раз эти кабанские корни кубического уравнения
>Можно также возводить в степень матрицу 3х3, там будет
>логарифмическая оценка времени.
А вот за это - спасибо. Я в очередной раз забыл о простых методах :)
← →
Alx2 © (2006-10-14 16:55) [36]>TUser © (14.10.06 16:48) [34]
Но в приведенном коде сложность все-таки меньше: O(T)= O(1) где T - период.
А модульная арифметика здесь дает логарифмическую сложность и для явной формулы.
← →
wl © (2006-10-14 17:51) [37]>ProgRAMmer Dimonych
для меня лично задача крайне сложная, можно узнать, почему она возникла? олимпиада какая-то или ?
← →
MeF Dei Corvi © (2006-10-14 18:04) [38]
> олимпиада какая-то или ?
Для олимпиады ИМХО слишком простая.
← →
default © (2006-10-14 18:11) [39]TUser © (14.10.06 16:37) [30]
это тоже решение за O(1) :)
только без формулы
← →
default © (2006-10-14 19:15) [40]кстати, вот ещё вам до кучи способ определения периода(правда не обязательно минимального, то есть возможно кратного минимальному)
комбинаций из трёх цифр, как уже говорилось, 1000
то есть в 1001 тройке цифр хотя бы две тройки цифр одинаковые
стало быть период, как минимум, начнётся с 1001 тройки, стало быть эта тысячная тройка заведомо часть периода
так вот идея в том чтобы заранее посчитать и хранить эту 1001 тройку
а в программе искать тройку с ней совпадающую с начала последовательности, обнаружили совпадение - получили период:)
никакой памяти дополнительной тут не требуется и программа упрощается заметно
← →
default © (2006-10-14 19:57) [41][40] не читать
кстати, вот ещё вам до кучи способ определения периода(правда не обязательно минимального, то есть возможно кратного минимальному)
способ, наверно, не больно эффективен, но - до кучи
комбинаций из трёх цифр, как уже говорилось, 1000
то есть в 1001 тройке цифр хотя бы две тройки цифр одинаковые
стало быть период, как минимум, начнётся с 1000 тройки, стало быть 1001 тройка заведомо часть периода
значит период будет от 1001 тройки до ближайшей тройки равной 1001
Страницы: 1 2 вся ветка
Форум: "Прочее";
Текущий архив: 2006.11.05;
Скачать: [xml.tar.bz2];
Память: 0.57 MB
Время: 0.061 c