Задачка для разминки мозга

← →
Sha © (2014-12-26 23:07) [40]

Если без больших чисел, то как-то так:

function LoSum(m, n: int64): int64; begin; Result:=0; while m>0 do begin Result:=Result+n mod m; m:=m-1; end; end; function HiSum(m, n: int64): int64; var i: integer; k: int64; begin; Result:=(n-m) * (n-m+1) shr 1; i:=1; while true do begin i:=i+1; k:=n div i; if k<m then exit; k:=(k+m) * (k-m+1) shr 1; Result:=Result-k; end; end; procedure TForm1.Button1Click(Sender: TObject); var m, n, sum: int64; begin; n:=1000; //sum:=LoSum(n,n); m:=trunc(sqrt(n+0.0)); sum:=LoSum(m,n)+HiSum(m+1,n); Memo1.Lines.Add(Format("%d %d",[n, sum])); end;

← →
Inovet © (2014-12-26 23:51) [41]

Удалено модератором

← →
Sha © (2014-12-27 02:30) [42]

Для 10^12 получилось $2740 F8DA4172 F914221E.
Наверно, где-то ошибка вкралась.

← →
MBo © (2014-12-27 09:20) [43]

То, что в короткую арифметику укладывается (до 10^10) - совпадает.

До меня пока не доходит принцип вычисления избытка в этой строчке:
k:=(k+m) * (k-m+1) shr 1;

← →
Sha © (2014-12-27 10:17) [44]

Это развитие той же идеи, что в [12]. Только мы проводим границу между левой и правой частью гораздо левее. Понятно, что первоначальное приближение результата, вычисленное в HiSum до цикла while, намного выше реального значения. Для k:=n div 2 и всех чисел левее (первая итерация) результат завышен по крайней мере (k+m) * (k-m+1) shr 1, где(k+m) - сумма первого и последнего элементов прогрессии, (k-m+1) - количество элементов. И т.д.

← →
Sha © (2014-12-27 12:18) [45]

*по крайней мере на

← →
Rouse_ © (2014-12-28 13:37) [46]

Вообще-то странно, у меня получается вот такое число:
0xEAF68 23E72F95 1E3AF012
т.е. явно на порядок больше чем $2740 или $2578.
Время рассчета около 4 секунд. Сейчас причешу код, расставлю каменты и отправлю Борису, пусть проверит, может я где ошибся - но не должен ибо все тесты показывают что результат должен быть именно такой.

← →
Rouse_ © (2014-12-28 13:50) [47]

Кстати 10 в 10-ой в короткую арифметику не влазит, ибо это уже 60 3DA5FCD5 412DF12B

← →
Rouse_ © (2014-12-28 13:52) [48]

Да, все верно, сейчас персчитал, максимум влазит 10 в 9-ой, это будет F660613D 7050BB60

← →
Sha © (2014-12-28 14:35) [49]

> Rouse_ © (28.12.14 13:37) [46]

По идее, младший dword ($F914221E) должен быть одинаковым для любой версии.

← →
Rouse_ © (2014-12-28 14:47) [50]

Если не учитывается то что Int64 знаковый, то совпадать не будет и будет ошибка при операциях сложения/вычитания.

← →
Rouse_ © (2014-12-28 14:48) [51]

Дай свое мыло я тебе тоже мое матобоснование вышлю через часик, перепроверишь. Может действительно у меня ошибка.

← →
Sha © (2014-12-28 14:50) [52]

мне на примере было бы понятней )

← →
Sha © (2014-12-28 14:54) [53]

Саш, мыло же есть у тебя. Ну или в моем бложике возьми.

А обоснование можно прям сюда или в свой блог выложить.

← →
Rouse_ © (2014-12-28 15:02) [54]

Я тебе с примером отправлю, сюда покачто еще рано, вот как вы с Борей меня перепроверите, тогда и выложу и сюда и на блог :)

← →
Rouse_ © (2014-12-28 15:34) [55]

Отправил обоим.

← →
Sha © (2014-12-28 16:00) [56]

Прочитал обоснование.

Идея очень похожа на [44]. Но реализация другая. И результат тоже другой. Буду искать причину. То, что для 10^9 результат совпадает, сильно упрощает задачу.

← →
MBo © (2014-12-28 17:53) [57]

>По идее, младший dword ($F914221E) должен быть одинаковым для любой версии.
Да, для 10^12 у меня так

← →
MBo © (2014-12-28 18:12) [58]

>Rouse_
Подставил свою арифметику (сложение) в твою процедуру, результат совпал с моим.
Так что принципиально все методы дают одинаковые результаты, различие кроется в длинной арифметике.

← →
MBo © (2014-12-28 18:36) [59]

>различие кроется в длинной арифметике.
Тьфу ты. нет же различий.
Вот вывод твоего присланного екзешника:
Input N or zero (0) for exit: 1000000000000 calculate... Result: 0x000000000000259814D6C9AAF914221E

← →
MBo © (2014-12-28 18:38) [60]

найди лишний нолик:
10000000000000 calculate... Result: 0x00000000000EAF6823E72F951E3AF012

← →
Rouse_ © (2014-12-28 18:45) [61]

> Так что принципиально все методы дают одинаковые результаты,
> различие кроется в длинной арифметике.

Ха :)
Эт я обшибся - мое число, это 10 в 13-ой степени :)))
А 10 в 12-ой, как раз 2598 14D6C9AA F914221E.
Значит все сошлось, сам всех запутал :)

← →
Rouse_ © (2014-12-28 18:45) [62]

> MBo © (28.12.14 18:38) [60]
> найди лишний нолик:
> 10000000000000
> calculate...

О, ты и сам отписался :)))
Ну да - моя ошибка :)

← →
Sha © (2014-12-28 23:24) [63]

[40] можно немного подсократить:

function Sum(n: int64): int64; var m, c: cardinal; i: int64; begin; c:=trunc(sqrt(n+0.0)); m:=c+1; dec(c, ord(int64(c)*c=n)); Result:=(n-m) * (n-m+1) shr 1; while c>1 do begin; i:=n div c; Result:=Result + n - i*c; //Result:=Result + n mod c; Result:=Result - (i+m) * (i-m+1) shr 1; dec(c); end; end;

← →
Sha © (2014-12-29 23:06) [64]

сейчас подумал: а ведь задачу никто не решил, число-то до сих пор так и не выведено )

← →
Rouse_ © (2014-12-30 10:20) [65]

Выведено, изначальная утилита работала почти три дня и показала это же число что у нас с MBo

← →
Sha © (2014-12-30 11:07) [66]

> Rouse_ © (30.12.14 10:20) [65]
> Выведено...

... в какой системе счисления? )

и эта, код давай )

← →
Rouse_ © (2014-12-30 11:55) [67]

> Sha © (30.12.14 11:07) [66]
> > Rouse_ © (30.12.14 10:20) [65]
> > Выведено...
>
> ... в какой системе счисления? )
>
> и эта, код давай )

Код? Какой, я ж тебе все отдал.
Код первого варианта в самом верху, код финальный я тебе отправлял :)

← →
Sha © (2014-12-30 12:27) [68]

Насколько я понимаю, входные и выходные данные в задаче должны быть представлены в десятичной системе счисления. Ты никогда не пробовал заплатить за пиво 3C рублей?

> Sha © (30.12.14 12:27) [68]
> Насколько я понимаю, входные и выходные данные в задаче
> должны быть представлены в десятичной системе счисления.

В условии задачи это не сказано, поэтому опустим сей момент :)

Ну а ответы на задачу (с исходниками) можно посмотреть вот тут: http://rouse-debug.blogspot.ru/2014/12/blog-post.html
Там все три готовых решения, от меня, от Mbo и от Sha.
Перекину на основной блог 1 января :)

> Ты никогда не пробовал заплатить за пиво 3C рублей?

А с каких пор число зависит от системы счисления? В любой системе продавец произнесёт: "с тебя шестьдесят рублей". Так что если продавец не глухонемой, то "стороннему наблюдателю" пофигу в какой системе счисления обозначены цены.

Ну на самом деле Sha тоже интересную задачу вбросил, ведь при конвертации разрядность аккумулятора выше диапазона десятичного числа. Но думаю что тут все-же это будет избыточно.

> Труп Васи Доброго © (30.12.14 14:06) [71]
> А с каких пор число зависит от системы счисления?

А кто сказал, что зависит? А вот не понять могут, когда начнешь искать свои 3C рублей.

Наверно, еще веселей будет, если продавец начнет просить у каждого Васи за пиво 3С рублей или на ценнике такое напишет.

задачка по-проще(надеюсь, не сильно баян):
дано число, состоящее из одних единиц
количество единиц - до 10^15
Найти остаток от деления на число, вплоть до пятизначного.

> разрядность аккумулятора выше

разрядность аккумулятора ниже

> картман © (30.12.14 14:18) [74]

А где пример входных и выходных данных?

> А где пример входных и выходных данных?

я решил ее концептуально, а дальше-то зачем? Конечно, могу на калькуляторе каком-нть посчитать, но боюсь ошибиться. Там особо нечего оптимизировать, нужно только догадаться.

для 10^12
В десятичном виде:
177532966574642659861022

Добавлено (сильно не тестировал, на паре значений совпадает с тем, что Windows.Calc даёт):
TUInt128 = record ... function DivMod10: Integer; function ToString: string; ... function TUInt128.DivMod10: Integer;//модифицирует число! var i, Rem: Integer; begin Rem := 0; for i := 15 downto 0 do begin Rem := Rem * 256 + Bytes[i]; Bytes[i] := Rem div 10; Rem := Rem mod 10; end; Result := Rem; end; function TUInt128.ToString: string; var Tmp: TUInt128; i, Len, Rem: Integer; Ch: Char; begin SetLength(Result, 40); Tmp.Lo := Lo; Tmp.Hi := Hi; Len := 1; repeat Rem := Tmp.DivMod10; Result[Len] := Char(Rem + Ord("0")); Inc(Len); until (Tmp.Hi = 0) and (Tmp.Lo = 0); Dec(Len); SetLength(Result, Len); for i := 1 to (Len) div 2 do begin Ch := Result[i]; Result[i] := Result[Len + 1 - i]; Result[Len + 1 - i] := Ch; end; end;

in: 111111111
17
out: 12

> MBo © (30.12.14 14:29) [78]
> для 10^12
> В десятичном виде:
> 177532966574642659861022

Ну вы блин...
Не, конвертацию делать мне уже лениво - новый год все таки, потому этот шаг без меня :)

Задачка для разминки мозга Найти похожие ветки