Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2015.09.10;
Скачать: CL | DM;

Вниз

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

 
Rouse_ ©   (2014-12-25 21:12) [0]

Пришлось тут на днях решать для студента (первого курса) задачку.
Дословно выглядит вот так:

2014 ACM-ICPC China Hunan Invitational Programming Contest

There is a simple problem. Given a number N.
You are going to calculate N%1+ N%2+ N%3+...+ N%N.

Input: The length N(1<=N<=10^12).

Output: Answer.

Sample input  5
Sample output 4


Вроде ничего сложного, однако-ж результат суммирования по модулю явно не уложится ни в один из поддерживаемых типов (int64 vfrcbvev 8 байт).

Сразу уточню: задачка олимпиадная, причем свежего 14-го года :)

Конечно странно что такие вещи задают первокурснику, но...

В итоге для первого приближения накидал такое решение:

// pk04_dop.cpp : Defines the entry point for the console application.
//

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

#include "stdafx.h"

// хранилище для оооочень большого числа
unsigned char UInt128[16];

void printUInt128(){
printf("result = 0x");
for (int i = 15; i >= 0; i--)
 printf("%hhX", UInt128[i]);
printf("\n");
}

// полный битовый сумматор реализующий таблицу истинности: http://ivatv.narod.ru/zifrovaja_texnika/1_04.htm
bool fullAdder(bool a, bool b, bool p0, bool *p){
// первый полусумматор
bool bRes = false;
*p = false;
if ((a && !b) || (b && !a))
 bRes = true;
if (a && b)
 *p = true;
if (!p0)
 return bRes;
// второй полусумматор
*p = true;
bRes = !bRes;
if (!a && !b)
 *p = false;
return bRes;
}

// сумматор на битовых операциях
void add(long long x){
bool pFlag = false;
unsigned long long halfResult = 0;
unsigned long long bigValue;
int i;
bool aBit, bBit, sFlag;

// получаем указатель на массив, содержащий большое число
unsigned long long *p;
p = (unsigned long long*)&UInt128[0];

// берем младшие 8 байт
bigValue = (unsigned long long)(*p);
for (i = 0; i < 64; i++){
 // и побитно, посредством полного сумматора складываем два числа
 aBit = ((unsigned long long)1 << i & x) > 0;
 bBit = ((unsigned long long)1 << i & bigValue) > 0;
 sFlag = fullAdder(aBit, bBit, pFlag, &pFlag);
 if (sFlag)
  halfResult |= (unsigned long long)1 << i;
};
// результат помещаем обратно
*p = halfResult;

// если нет переноса бит от предыдущей операции, то можно выходить
if (!pFlag)
 return;

halfResult = 0;

// сдвигаемся на 8 байт
p++;

// берем старшие 8 байт
bigValue = (unsigned long long)(*p);
for (i = 0; i < 64; i++){
 // увеличиваем значение описаясь на бит переноса
 bBit = ((unsigned long long)1 << i & bigValue) > 0;
 sFlag = fullAdder(false, bBit, pFlag, &pFlag);
 if (sFlag)
  halfResult |= (unsigned long long)1 << i;
};
// результат помещаем обратно
*p = halfResult;
}

int _tmain(int argc, _TCHAR* argv[])
{
unsigned long long a, i;

printf("enter value: ");
scanf("%lld", &a);

printf("calculating...\n");
i = a;
while(i > 0){
 add(a % i);
 i--;
};
printUInt128();

getchar();
getchar();

return 0;
}


Сразу скажу - ЭТО работает, причем работает правильно (можно даже использовать для проверки), однако есть более грамотный и более быстрый вариант решения в 17 строчек кода (на дельфи или на си - кому как удобнее) :)


 
Kerk ©   (2014-12-25 21:26) [1]


> Вроде ничего сложного, однако-ж результат суммирования по
> модулю явно не уложится ни в один из поддерживаемых типов
> (int64 vfrcbvev 8 байт).

Не уверен.
Максимальное значение Int64 сильно больше, чем 10^12. При этом ни один из остатков не может превысить 10^2 / 2.

Эта задача скорее на знание чего-нибудь хитрого из теории чисел, имхо.


 
Kerk ©   (2014-12-25 21:26) [2]


> не может превысить 10^12 / 2.

единицу потерял


 
Rouse_ ©   (2014-12-25 21:27) [3]

Вот так будет на дельфи, если у кого затруднения:

program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
 Windows,
 System.SysUtils,
 Math;

type
 Int128 = array [0..15] of Byte;

var
 VeriBigInteger: Int128;

procedure PrintInt128;
var
 I: Integer;
begin
 Write("0x");
 for I := 15 downto 0 do
   Write(IntToHex(VeriBigInteger[I], 2));
 Writeln;
end;

function FullAdder(A, B, P0: Boolean; var P: Boolean): Boolean;
begin
 Result := False;
 P := False;
 if A and not B then
   Result := True;
 if B and not A then
   Result := True;
 if A and B then
   P := True;
 if not P0 then Exit;
 P := True;
 Result := not Result;
 if not A and not B then
   P := False;
end;

procedure Add(Value: Int64);
var
I: Integer;
ABit, BBit, SFlag, PFlag: Boolean;
HalfResult, BigValue: Int64;
begin
PFlag := False;
HalfResult := 0;
BigValue := PInt64(@VeriBigInteger[0])^;
for I := 0 to 63 do
begin
  ABit := (Int64(1) shl I and Value) > 0;
  BBit := (Int64(1) shl I and BigValue) > 0;
  SFlag := FullAdder(ABit, BBit, PFlag, PFlag);
  HalfResult := HalfResult or (Int64(SFlag) shl I);
end;
PInt64(@VeriBigInteger[0])^ := HalfResult;

HalfResult := 0;
BigValue := PInt64(@VeriBigInteger[8])^;
for I := 0 to 63 do
begin
  BBit := (1 shl I and BigValue) > 0;
  SFlag := FullAdder(False, BBit, PFlag, PFlag);
  HalfResult := HalfResult or (Byte(SFlag) shl I);
end;

PInt64(@VeriBigInteger[8])^ := HalfResult;
end;

function TstNative(X: int64): int64;
var
 I: Int64;
begin
 I := X;
 Result := 0;
 while I > 0 do
 begin
   Result := Result + (X mod I);
   Dec(I);
 end;
end;

procedure TstOld(X: int64);
var
 I: Int64;
begin
 ZeroMemory(@VeriBigInteger[0], SizeOf(Int128));
 I := X;
 while I > 0 do
 begin
   Add(X mod I);
   Dec(I);
 end;
 PrintInt128;
end;

var
 N: int64;
begin
 try
 repeat
   Readln(N);
   Writeln("0x", IntToHex(TstNative(N), 32));
   TstOld(N);
 until N = 0;
 except
   on E: Exception do
     Writeln(E.ClassName, ": ", E.Message);
 end;
 readln;
end.


 
Rouse_ ©   (2014-12-25 21:28) [4]


> Не уверен.
> Максимальное значение Int64 сильно больше, чем 10^12. При
> этом ни один из остатков не может превысить 10^2 / 2.

Так этож входное значение, а нужно просчитать сумму всех чисел по модулю yfxbyfz jn Т до нуля. Она там за глаза выходит за Int64


 
Inovet ©   (2014-12-25 21:35) [5]

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


 
Kilkennycat ©   (2014-12-25 21:41) [6]

...N%1...
a % что означает?


 
Inovet ©   (2014-12-25 21:42) [7]

Ну и это... в цикле гнать всю сумму как-то тупо. Здесь должно решаться математически, типа получается сумма целых от 1 до N, а это чё там такое N*(N-1)/2 что ли? Как-то просто слишком, а ну так длинное же и не влазит никуда.


 
Inovet ©   (2014-12-25 21:44) [8]

> [6] Kilkennycat ©   (25.12.14 21:41)
> a % что означает?

Это деление по модулю


 
Rouse_ ©   (2014-12-25 21:53) [9]


> a % что означает?

аналог MOD


 
Rouse_ ©   (2014-12-25 21:55) [10]


> а это чё там такое N*(N-1)/2

Откуда ты это взял? Нет там такого. Там есть диапазон от 0 до 10 в 12-ой степени, в пределах которого мыжет быть N


 
Kerk ©   (2014-12-25 22:13) [11]


> Так этож входное значение, а нужно просчитать сумму всех
> чисел по модулю yfxbyfz jn Т до нуля. Она там за глаза выходит
> за Int64

Максимальное значение суммы какое получается? Я в четверг вечером не готов посчитать :)

В целом, надо с другой стороны заходить. Олимпиады так в лоб не работают. Я запустил твою считалку полчаса назад, она до сих пор считает.

Например, можно разбить ряд на две части.

Одна часть будет
N%1 + N%2+ N%3 + ... + N%(N / 2)

Вторая часть
N%(N / 2 + 1) + N%(N / 2 + 1) + ... + N%N

Сумма второй части считается легко. Это банальная арифметическая прогрессия X*(X+1)/2, где X = ((N - 1) div 2).

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


 
MBo ©   (2014-12-25 22:14) [12]

>Откуда ты это взял? Нет там такого
Похожее есть. Сумма второй половины слагаемых Sh находится нетрудно без сложения.
M = (N - 1) div 2
Sh = M * (M + 1) / 2


 
Inovet ©   (2014-12-25 22:15) [13]

> [10] Rouse_ ©   (25.12.14 21:55)
> Нет там такого.

Ну значит я не понял вот это
N%1+ N%2+ N%3+...+ N%N


 
Rouse_ ©   (2014-12-25 22:19) [14]


> Максимальное значение суммы какое получается? Я в четверг
> вечером не готов посчитать :)
>
> В целом, надо с другой стороны заходить. Олимпиады так в
> лоб не работают. Я запустил твою считалку полчаса назад,
>  она до сих пор считает.

Ага, у меня тоже, даже оптимизированный вариант, но уже значение вышло за диапазон 8 байт :)


> MBo ©   (25.12.14 22:14) [12]
> >Откуда ты это взял? Нет там такого
> Похожее есть. Сумма второй половины слагаемых Sh находится
> нетрудно без сложения.
> M = (N - 1) div 2
> Sh = M * (M + 1) / 2

Ну что-то примерно похожее: 12499999999999999999999999,875


 
Kerk ©   (2014-12-25 22:21) [15]


> X*(X+1)/2, где X = ((N - 1) div 2).

И даже при N = 10^12 сумма второй части получается намного меньше Int64 :)


 
Inovet ©   (2014-12-25 22:29) [16]

> [14] Rouse_ ©   (25.12.14 22:19)
> Ну что-то примерно похожее: 12499999999999999999999999,875

Это для какого N?
калькулятор Windows для 10^12
500 000 000 000 500 000 000 000


 
Inovet ©   (2014-12-25 22:32) [17]

124 999 999 999 750 000 000 000


 
Kerk ©   (2014-12-25 22:33) [18]


> намного меньше Int64 :)

Неправильно посчитал, действительно может вылезти.

Ну в любом случае, просто суммировать - не выход.
Насчет первой части тоже нужно что-то математическое придумать.


 
jack128 ©   (2014-12-25 23:11) [19]


> Ну в любом случае, просто суммировать - не выход.

почему не выход?


 
jack128 ©   (2014-12-25 23:18) [20]


> Насчет первой части тоже нужно что-то математическое придумать.

Насколько я понимаю, начиная с I := N/3+1 до N/2 - 1 остаток будет прогрессией от 1 до N/3 - 1


 
Kerk ©   (2014-12-25 23:18) [21]

Долго потому что. Должна быть возможность решить за разумное время. Это же олимпиадная задачка. Такие задачи изначально не рассчитаны на то, чтоб их по часу считать.


 
Rouse_ ©   (2014-12-25 23:30) [22]

Оптимизированный вариант на максимальном значении работает около 6 секунд, не думаю что это сильно долго :) финальное число пока не называю, бо интрига :)


 
Rouse_ ©   (2014-12-25 23:31) [23]

Кстати жек, тыж алго решения знаешь, проверь у себя, у тебя такое же время выходит?


 
Sha ©   (2014-12-26 10:24) [24]

> MBo ©   (25.12.14 22:14) [12]
> Сумма второй половины слагаемых Sh находится нетрудно без сложения.

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


 
MBo ©   (2014-12-26 10:28) [25]

Сделал решение за асимптотическое время Sqrt(N) (т.е. порядка нескольких миллионов операций для 10^12, считается мгновенно).
А вот арифметику для 128 бит, вероятно, реализовал с ошибками, отлаживать пока некогда.
Для N = 1000 получается 176919, что совпадает со значением, вычисленным в рамках простой арифметики.
для N = 1000000000000 получается результат со старшим int64-словом $257A=9594 ~ 176*10^21. Младший и старший байты $E0 и $25


 
Rouse_ ©   (2014-12-26 12:10) [26]

А как делал?
Через рассчет нижнего и верхнего лимитов арифметических прогрессий?


 
MBo ©   (2014-12-26 12:28) [27]

Через сумму квадратов с чередующимися знаками.
Поправка по моим числам (упустил в обном месте возможность переполнения, не уверен, что ещё чего-то не осталось):
старшее слово $2578=9592 ~ 176*10^21. Младший и старший байты $1E и $25


 
MBo ©   (2014-12-26 13:14) [28]

Еще одна итерация ;)
старшее слово $2598=9624 ~ 177*10^21. Младший и старший байты $1E и $25


 
Rouse_ ©   (2014-12-26 13:36) [29]

Во как - я по другому ускорял... как доделаешь - покажи, можно для начала в приват rouse79@yandex.ru


 
Плохиш ©   (2014-12-26 14:19) [30]


> Вроде ничего сложного, однако-ж результат суммирования по
> модулю явно не уложится ни в один из поддерживаемых типов
> (int64 vfrcbvev 8 байт).

Составитель читал книгу Вирта "Описание языка паскаль" и сподобился заменить формулу расчёта факториала своей :-)


 
Rouse_ ©   (2014-12-26 14:27) [31]


> Плохиш ©   (26.12.14 14:19) [30]
> Составитель читал книгу Вирта "Описание языка паскаль" и
> сподобился заменить формулу расчёта факториала своей :-)

Развивай мысль :)


 
MBo ©   (2014-12-26 14:36) [32]

>Rouse_ ©   (26.12.14 13:36) [29]
Отослал


 
Rouse_ ©   (2014-12-26 14:42) [33]

Угу вечером гляну.
Мой вариант данное число вычисляет за
Z := 10000000000000 div 900000;
используя две вершины каждого из пиков.
т.е. цикл крутится порядка полутора секунд, но еще не до конца допилен (это третий вариант решения).
Твой будет четвертым получается :)


 
Rouse_ ©   (2014-12-26 15:47) [34]

Глянул - суматор для 128 бит у тебя верный, один в один можно сказать. А вот остальной подход пока никто из нашего отдела не понял с квадратами, правда у нас корпоратив и сложно сходу в код вникнуть... :)


 
Inovet ©   (2014-12-26 19:35) [35]

- Я потерял нить рассуждения?
Собеседник отвечает, глядя в сторону остальных участников,
- По-моему, он потерял не только нить.


 
Rouse_ ©   (2014-12-26 20:04) [36]


> Inovet ©   (26.12.14 19:35) [35]

Я отвечал MBo :)
А так-то вообще мой подход (уход от цикла через рассчет арифметической прогрессии, порционно по 900 тысяч элеменов) с посказками доступен тут: http://alexander-bagel.blogspot.ru/2014/12/blog-post.html
Почему именно 900 тысяч? Ну округлил. А так база была - максимальная сумма деления по модулю от 10 в 12-ой которая при суммировании влезет в 8 байт.


 
MBo ©   (2014-12-26 20:41) [37]

Функции 128-битной арифметики, которые мне были нужны (не обрабатываются ситуации, которые исключены в данной задаче):

 TUInt128 = record
   class operator Add(a, b: TUInt128): TUInt128;
   class operator Subtract(a, b: TUInt128): TUInt128;
   class operator Implicit(Value: UInt64): TUInt128;
   class function Sqr128(Value: TUInt128): TUInt128; static;
   case Integer of
     0:        (Lo, Hi: UInt64);
     1:        (LoLo, LoHi, HiLo, HiHi: Cardinal);
     2:        (Bytes: array [0 .. 15] of Byte);
 end;

{ TUInt128 }

class operator TUInt128.Add(a, b: TUInt128): TUInt128;
begin
 if a.Lo > UInt64($FFFFFFFFFFFFFFFF) - b.Lo then
   Inc(a.Hi);
 Result.Lo := a.Lo + b.Lo;
 Result.Hi := a.Hi + b.Hi;
end;

class operator TUInt128.Implicit(Value: UInt64): TUInt128;
begin
 Result.Hi := 0;
 Result.Lo := Value;
end;

class function TUInt128.Sqr128(Value: TUInt128): TUInt128;
var
 ad: TUInt128;
begin
 Result.Hi := UInt64(Value.LoHi) * Value.LoHi;
 Result.Lo := UInt64(Value.LoLo) * Value.LoLo;
 ad.Lo := UInt64(Value.LoHi) * Value.LoLo;
 ad.Hi := ad.LoHi;
 ad.Lo := ad.Lo shl 32;
 Result := Result + ad;
 Result := Result + ad;
end;

class operator TUInt128.Subtract(a, b: TUInt128): TUInt128;
begin
 if a.Lo < b.Lo then
   Dec(a.Hi);
 Result.Lo := a.Lo - b.Lo;
 Result.Hi := a.Hi - b.Hi;
end;



 
MBo ©   (2014-12-26 21:19) [38]

Вот начало ряда сумм S(N) и модули, из которых эти суммы складываются.

N   S     mods  
1   0      0  
2   0      0  0  
3   1      0  1  0
4   1      0  0  1  0
5   4      0  1  2  1  0
6   3      0  0  0  2  1  0
7   8      0  1  1  3  2  1  0
8   8      0  0  2  0  3  2  1  0
9  12      0  1  0  1  4  3  2  1  0
10 13      0  0  1  2  0  4  3  2  1  0
11 22      0  1  2  3  1  5  4  3  2  1  0
12 17      0  0  0  0  2  0  5  4  3  2  1  0
13 28      0  1  1  1  3  1  6  5  4  3  2  1  0

Видно, что правая часть представляет собой арифм. последовательность, сумму которой я уже приводил, а вот левая похитрее. Компактного математического выражения не нашел, но эмпирическое исследование привело к следующему:
главный член суммы резко растет на каждом втором (нечетном) числе, рост квадратичный, и это квадрат выражения (N-1) div 2
Q1 = Sqr((N-1) div 2)
Теперь, если вывести разницу Q1 - S(N), то можно увидеть, что она чаще всего скачет на каждом третьем числе, а сдвиг от начала будет уже 3
Q2 = -Sqr((N-3) div 3)
Далее аналогично
Q3 = Sqr((N-6) div 4)
Q4 = -Sqr((N-10) div 5)
и т.д. Числа сдвига - "треугольные", вида k(k-1)/2, где k - знаменатель.

Итого с использованием длинной арифметики получается функция, которая отличается от такой же для короткой арифметики только типом результата и заменой Sqr на TUint128.Sqr128 (если Multiply реализовать, то в обоих случаях можно одинаково X*X)  

 function SumOfMods128(N: Int64): TUInt128;
 var
   Minus, Divider: UInt64;
   Even: Boolean;
 begin
   Result := 0;
   Minus := 1;
   Divider := 2;
   Even := True;
   while Minus < N do begin
     if Even then
       Result := Result + TUint128.Sqr128((N - Minus) div Divider)
     else
       Result := Result - TUint128.Sqr128((N - Minus) div Divider);
     Minus := Minus + Divider;
     Divider := Divider + 1;
     Even := not Even;
   end;
 end;


 
Плохиш ©   (2014-12-26 22:53) [39]


> Rouse_ ©   (26.12.14 14:27) [31]
>
>
> > Плохиш ©   (26.12.14 14:19) [30]
> > Составитель читал книгу Вирта "Описание языка паскаль"
> и
> > сподобился заменить формулу расчёта факториала своей :
> -)
>
> Развивай мысль :)

Там был приведён код расчёта факториала для любых чисел с выводом результата :-)
Результат хранился в массиве строк или символов, точно не помню. Почти 20 лет прошло.


 
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 рублей?


 
Rouse_ ©   (2014-12-30 13:17) [69]


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

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

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


 
Inovet ©   (2014-12-30 13:25) [70]

> [68] Sha ©   (30.12.14 12:27)
> за пиво 3C рублей

Это надо в специальное кафе для программистов идти.


 
Труп Васи Доброго ©   (2014-12-30 14:06) [71]


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

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


 
Rouse_ ©   (2014-12-30 14:13) [72]

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


 
Sha ©   (2014-12-30 14:15) [73]

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

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

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


 
картман ©   (2014-12-30 14:18) [74]

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


 
Rouse_ ©   (2014-12-30 14:21) [75]


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

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


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

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


 
картман ©   (2014-12-30 14:24) [76]


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

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


 
Rouse_ ©   (2014-12-30 14:26) [77]


> картман ©   (30.12.14 14:24) [76]

Да просто пример дай, как в моей задаче :))

In: 101
Out: 2

Как-то так :)


 
MBo ©   (2014-12-30 14:29) [78]

для 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;



 
картман ©   (2014-12-30 14:29) [79]

in: 111111111
    17
out: 12


 
Rouse_ ©   (2014-12-30 14:54) [80]


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

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


 
Rouse_ ©   (2014-12-30 14:56) [81]


> картман ©   (30.12.14 14:29) [79]
> in: 111111111
>     17
> out: 12
>
>

17 это что?
У тебя введено 9 единиц (69F6BC7 в хексе).


 
Sha ©   (2014-12-30 15:09) [82]

> Rouse_ ©   (30.12.14 14:54) [80]

а тут выбор только в размере шага (byte, word или dword) - классика

> Rouse_ ©   (30.12.14 14:56) [81]

111111111 mod 17 = 12


 
Rouse_ ©   (2014-12-30 15:14) [83]


> Sha ©   (30.12.14 15:09) [82]
> > Rouse_ ©   (30.12.14 14:54) [80]
>
> а тут выбор только в размере шага (byte, word или dword)
> - классика


Да я в курсе - просто лень :)


> 111111111 mod 17 = 12

А, там же еще второе число :) Надо завязывать программировать в предновогодние прадники :)


 
Rouse_ ©   (2014-12-30 15:15) [84]

Кстати Саш, все еще жду матобоснование твоего подхода. Проверь почту.


 
Rouse_ ©   (2014-12-30 16:56) [85]

Выложил матобоснование от Sha.
Сань - ты монстр как есть :)


 
Sha ©   (2014-12-30 17:24) [86]

> Rouse_ ©   (30.12.14 16:56) [85]

какой нафиг монстр, если линейный конгруэнтный метод вспомнил минут через 10 после [74] )



Страницы: 1 2 3 вся ветка

Текущий архив: 2015.09.10;
Скачать: CL | DM;

Наверх




Память: 0.71 MB
Время: 0.075 c
15-1417125008
Kerk
2014-11-28 00:50
2015.09.10
I don’t always use Delphi, but when I do…


15-1420742668
Kerk
2015-01-08 21:44
2015.09.10
О безопасности программ на Delphi


6-1275567216
Eraser
2010-06-03 16:13
2015.09.10
Высоконагруженный TCP сервер


2-1393017198
Novicer
2014-02-22 01:13
2015.09.10
Как правильно установить Firebird?


8-1236108535
Ем растишку - летаю
2009-03-03 22:28
2015.09.10
Delphi + .icc color profiles