[Algorytm] Numery domow

0

Witam, znalazlem takie zadanko

Pewien informatyk zwykł spacerować po ulicy na której stał jego dom. Kiedyś, z nudów, policzył sumę numerów domów obok których przechodził. Zauważył, że suma jest taka sama kiedy idzie w lewo do końca ulicy (gdzie numery są coraz mniejsze) i kiedy idzie w prawo (gdzie numery są coraz większe). Bardzo mu się to spodobało i postanowił, że od tej chwili każdy z kupowanych przez niego domów będzie miał tą własność. Napisz program, który znajdzie pierwsze 10 par: numer domu, ilość domów na ulicy, które spełniają tą własność. Zakładamy, że informatyk nie liczył swojego numeru i że numery na ulicy to kolejne liczby naturalne. Dwie pierwsze takie pary to: 6,8 oraz 35,49.

i probuje je rozwiazac :))
napisalem naiwny algorytm i mam pytanie czy ktos zna jakis sposob na wyszukanie tych rozwiazan w jakis szybszy sposob albo zna odpowiedz na pytanie czy jest ich skonczona ilosc, jesli tak to dlaczego?
pozdrawiam

A to jest co udalo mi sie naskrobac :)
[code]
program numery_domow_3_0;

{$APPTYPE CONSOLE}

uses
SysUtils;

var
znaleziono:Byte;
nr_domu,l_all,suma_l,suma_p:int64;

begin
nr_domu:=2;
l_all:=3;
znaleziono:=0;
suma_p:=3;
suma_l:=1;
while znaleziono<12 do
begin
while suma_p<suma_l do
begin
l_all:=l_all+1;
suma_p:=suma_p+l_all;
end;
if (suma_p=suma_l) then
begin
znaleziono:=znaleziono+1;
writeln(znaleziono:2,': ',nr_domu,', ',l_all);
end;
suma_l:=suma_l+nr_domu;
nr_domu:=nr_domu+1;
suma_p:=suma_p-nr_domu;
end;
write('koniec');
readln;
end.
[/code]

Jeszcze raz pozdro i z gory dzieki

0

Załóżmy, że jest n domów i informatyk mieszka w domu o numerze k. n>k, k>=3.

Suma numerów domów na lewo od informatyka wynosi:
1+2+...+(k-1) = (k-1)k/2,
zaś na prawo:
(k+1)+...+n = n
(n+1)/2 - k*(k+1)/2

Z treści wynika, że te sumy mają być równe, czyli otrzymujemy 2k2=n*(n+1). Dalej to już prosto k2=n*(n+1)/2. Ustalamy n i liczymy k ;) Z uwagi na błędy zaokrągleń (sqrt) można szukać k w pętli liczącej w dół od wartości Podłoga[Sqrt(n*(n+1)/2)]+1.

pzdr,

y.

0

Tak, tylko ze to nie zmenia faktu, ze i tak trzeba puscic petelke po wszystkich liczbach naturalnych. O ile nie ma to znaczenia przy pierwszych 8-10 rozwiazaniach to juz kolejnych nie da sie tym sposobem wyszukac (wartosci wykraczaja poza zakres zmiennych podczas mnozenia). Chodzilo mi o sposob pozbycia sie jak najwiekszej liczby operacji w sensie przeskoku do miejsca od ktorego warto by zaczac poszukiwanie kolejnego rozwiazania. Mi udalo sie dojsc do 12: numer domu informatyka to 1583407981 a wszystkich domow jest 2239277041. Kto da wiecej i w jaki sposob, a moze to juz ostatnie rozwiazanie?

pozdro

0

Hmm, no to na razie dwie propozycje:

  1. zaimplementuj własną arytmetykę na dużych liczbach całkowitych
  2. skorzystaj z tego, że reszta kwadratu liczby całkowitej w dzieleniu przez 10 należy do zbioru {0,1,4,5,6,9}, a to już ogranicza ilość liczb o połowę. n*(n+1) = 2k^2 (mod 10). Kongruencje modulo ta sama liczba można mnożyć stronami. Dziś nie mam zbyt dużo czasu, żeby dalej z tym kombinować, więc pomyśl sam. Myślę, że chińskie twierdzenie o resztach może okazać się pomocne, ale głowy nie dam sobie za to uciąć.

pzdr,

y.

0

A nie lepiej pomyslec o sumie na ciag arytmetyczny?

1 użytkowników online, w tym zalogowanych: 0, gości: 1