Смотрю на задачу, как баран на новые ворота...

← →
ProgRAMmer Dimonych © (2007-01-02 16:59) [0]

хотя, вроде как, сильно Новый год не праздновал. Имеется задача по теме "рекуррентные соотношения".

Найти сумму квадратов всех положительных целых чисел, запись которых в десятичной системе счисления состоит ровно из k отличных от 0 цифр.

Пробую сократить явно избыточный текст программы...

Найти сумму квадратов всех натуральных чисел, состоящих из k ненулевых цифр.

Перечитываю и офигеваю:

1. Уже при k=2 на трубопаскакале в Integer поместиться не дано (там число знаков из 8, десятичных). Получается, длинная арифметика нужна. Ладно, прорвёмся!!!
2. Вау, а где ж рекурсия-то? В смысле "рекуррентные соотношения"? каким образом зависит сумма квадратов для k=2 от того же, но при k=1?

Неужели придётся долбить глухой цикл с перебором всех чисел, возведением их в квадрат и "плюсованием" к огромной сумме (не меньше 2k цифр - по самым приблизительным предположениям)? В чём тут может быть прикол?

← →
ferr © (2007-01-02 17:02) [1]

а тема тебе ни о чём не говорит?

← →
ProgRAMmer Dimonych © (2007-01-02 17:10) [2]

> ferr © (02.01.07 17:02) [1]
Ех, я ж вот и говорю:
> Смотрю на задачу, как баран на новые ворота...
> хотя, вроде как, сильно Новый год не праздновал.
> 2. Вау, а где ж рекурсия-то? В смысле "рекуррентные соотношения"?
> каким образом зависит сумма квадратов для k=2 от того же,
> но при k=1?
:(

← →
ferr © (2007-01-02 17:11) [3]

3 2 1/3 (n + 1) - 1/2 (n + 1) + 1/6 n + 1/6
вот по этой формуле можно найти суммы квадратов всех чисел от 1 до n. Из её результата надо будет вычетать числа составленный хотя б из нуля. Их сумму квадратов надо полуать реккурентно.

P.S. в первом приближении так.

← →
ProgRAMmer Dimonych © (2007-01-02 17:32) [4]

> ferr © (02.01.07 17:11) [3]
3 и 2 над строкой - это степени?

В целях повышения уровня образованности ((С) Postmaster Pechkin), как вообще эта формула обзывается и из какой она оперы? (Надеюсь, не 7.1 ;))

> P.S. в первом приближении так.
Второе приближение я надеюсь выполнить уже самостоятельно. Главное - это, так {неприлично} сказать, толчок :)

← →
Sha © (2007-01-02 17:37) [5]

Никто не запрещал сумме квадратов зависеть еще и от обычной суммы.
Считай простую сумму и сумму квадратов на каждой итерации и будет счастье.

← →
ferr © (2007-01-02 17:41) [6]

> 3 и 2 над строкой - это степени?
>
> В целях повышения уровня образованности ((С) Postmaster
> Pechkin), как вообще эта формула обзывается и из какой она
> оперы? (Надеюсь, не 7.1 ;))

да, степени, если не веришь проверяй индукцией)

← →
ProgRAMmer Dimonych © (2007-01-02 17:50) [7]

> ferr © (02.01.07 17:41) [6]
Спасибо за помощь.

> Sha © (02.01.07 17:37) [5]
А каким образом сумма квадратов зависит от обычной суммы? Подозреваю, что это что-то из 11 класса и старше... Я прав?

← →
Virgo_Style © (2007-01-02 17:59) [8]

В свое время меня просто-таки поразил такой факт:

1 = 1
1+3 = 4
1+3+5 = 9
1+3+5+7 = 16
1+3+5+7+9 = 25
...
т.е., сумма N нечетных чисел, начиная с 1, равна квадрату N.
Хотя объясняется вполне логично и даже элементарно)

← →
Sha © (2007-01-02 17:59) [9]

Если разложить все твои K-значные числа по последней цифре, например:
12345=1234*10+5
записать их друг под другом и возвести в квадрат,
то увидишь, что К-ая сумма квадратов зависит от
K, К-1ой суммы квадратов, К-1ой суммы, 1ой суммы квадратов, 1ой суммы.
Вот тебе и формула.
Может упростишь там че-нить.

← →
default © (2007-01-02 18:01) [10]

тема "рекуррентные соотношения" и значит мыслить надо рекуррентно

предпологаем, что мы уже знаем сумму квадратов k-значных чисел(без нулей) и нужно найти сумму квадратов k+1 значных чисел(тоже без нулей)

пусть k=2
и возьмём k+1=3-значное число 327
тогда можно записать (3*100+27)^2=3^2*10^4+27^2+3*2*100*27

теперь мы смекаем, что результирующий ряд для k+1=3-значных чисел будет таким
[ [9^2(-это количество двузначных чисел)*(1^2*10^4)+1*2*10^2*(
сумма двузначных чисел без нулей - её сам сообразишь как считать)]
+...+
[9^2(-это количество двузначных чисел)*(9^2*10^4)+9*2*10^2*(
сумма двузначных чисел - её сам сообразишь как считать)] ]
+9*сумма квадратов двузначных чисел
при преобразованиях потребуется формула из [3] и формула суммы арифметической прогрессии
+"сумма двузначных чисел без нулей - её сам сообразишь как считать"

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

← →
Sha © (2007-01-02 18:09) [11]

Вот default предлагает разложить по первой цифре.
Дело вкуса - по-любому правильно.

← →
ProgRAMmer Dimonych © (2007-01-02 18:15) [12]

ОК, всем спасибо, буду разбираться.

procedure TForm1.Button9Click(Sender: TObject); var Sum1, Square1, Sum, Square, Power: int64; t1, t2, d, s: int64; i, k: integer; label ZeroFound; begin k:=5; Sum:=0; for i:=1 to 9 do Sum:=Sum + int64(i); Square:=0; for i:=1 to 9 do Square:=Square + int64(i) * int64(i); Sum1:=Sum; Square1:=Square; Power:=1; for i:=2 to k do begin; Power:=Power * 9; Square:=900 * Square + Power * Square1 + 20 * Sum * Sum1; Sum:=90 * Sum + Power * Sum1; end; //проверка t2:=1; for i:=1 to k do begin; t1:=t2; t2:=t2 * 10; end; s:=0; while t2>t1 do begin; d:=t2; while d>0 do begin; if d mod 10=0 then goto ZeroFound; d:=d div 10; end; s:=s + t2 * t2; ZeroFound: t2:=t2-1; end; ShowMessage(Format("%d"#13#10"%d"#13#10"%d"#13#10,[Square,s,Square-s])); end;

Не так.
Просто ты параболу первый раз нарисовал, когда был в три раза старше )
Этот факт все замечают, когда параболу рисуют.

> Virgo_Style © (02.01.07 21:03) [15]

Не знаю. :) Но прочитал недавно. Тут же вспомнился Гаусс, который посчитал сумму чисел для уставшей учительницы от 1 до 100 в 7 лет. Кому что в 5-7 лет, а им такое уже. :)

Sha © (02.01.07 21:07) [16]
давно это было, но imho не так... Факт-то, наверное, заметил, но проверить, для любых ли это чисел выполняется, не додумался)

Нет, мне-таки до них далеко, потому что, если мне не изменяет память, это я заметил все-таки тогда, когда об этом где-то прочитал)))

Смотрю на задачу, как баран на новые ворота... Найти похожие ветки