задуманно натуральное число х.известны три числа- остатки от деления этого числа 3,5,7 - i,j,k соответсвенно. найти Х
klem4
24.10.2006 21:57
а что непонятного ?
X mod 3 = a X mod 5 = b X mod 7 = c
a, b, c - известны
Задача кстати решалась, можно поискать.
Гость
24.10.2006 22:06
х=3l*i x=5m*j x=7t*k
потом типа 3l*i=5m*j
так объяснили
volvo
24.10.2006 22:18
Sofo4ka, простым перебором чисел находишь те, что удовлетворяют заданным условиям. Этого тебе вполне хватит (все официальные решения с олимпиад этой задачи основывались именно на переборе - проблем ни у кого не возникло...)
Sofo4ka
25.10.2006 13:44
а у мя возникла )
volvo
25.10.2006 13:48
В чем именно?
Запустить цикл от 1 до 32767 (максимально возможное число для Integer), и для каждого числа проверять равенство остатков от его деления на 3, 5, 7 числам i, j, k соответственно?
klem4
25.10.2006 14:10
Вот что я придумал :
uses crt; var i, j, k: Integer; c1, c2, c3, a, b, c: Integer; find: boolean;
while (c1 < maxint) and not(find) do begin a := c1 * 3 + i; c2 := 1; while (c2 < maxint) and not(find) do begin b := c2 * 5 + j; if b > a then break; c3 := 1; while (c3 < maxint) and not(find) do begin c := c3 * 7 + k; if (c > b) or (c > a) then break; find := ((a = b) and (a = c)); inc(c3); end; inc(c2); end; inc(c1); end;
if find then writeln(a) else writeln('No found !');
readln; end.
Вот только будет ли это быстрее обычного перебора
klem4
25.10.2006 14:37
Невероятно
global := 0; t1 := GetTickCount;
repeat while (c1 < maxint) and not(find) do begin a := c1 * 3 + i; c2 := 1; while (c2 < maxint) and not(find) do begin b := c2 * 5 + j; if b > a then break; c3 := 1; while (c3 < maxint) and not(find) do begin c := c3 * 7 + k; if (c > b) or (c > a) then break; find := ((a = b) and (a = c)); inc(c3); end; inc(c2); end; inc(c1); end;
inc(global); until global = 900000;
writeln('Result = ',a);
t2 := GetTickCount; writeln('Time1 = ', t2 - t1);
global := 0; t1 := GetTickCount;
repeat for p := 1 to maxint do if (p mod 3 = i) and (p mod 5 = j) and (p mod 7 = k) then break; inc(global); until global = 900000;
t2 := GetTickCount; writeln('Time2 = ', t2 - t1);
writeln('Result = ', p);
volvo
25.10.2006 14:56
Цитата
Невероятно
Потому, что некорректно Ты же не инициализируешь Find и C1 заново при каждой итерации, следовательно, у тебя в первом случае показывается время одной итерации, а во втором - время ВСЕХ... Вот так - корректнее:
uses windows, crt; var i, j, k: Integer; c1, c2, c3, a, b, c, p, global: Integer; find: boolean;
global := 0; repeat find := false; c1 := 0; while (c1 < maxint) and not(find) do begin a := c1 * 3 + i; c2 := 1; while (c2 < maxint) and not(find) do begin b := c2 * 5 + j; if b > a then break; c3 := 1; while (c3 < maxint) and not(find) do begin c := c3 * 7 + k; if (c > b) or (c > a) then break; find := ((a = b) and (a = c)); inc(c3); end; inc(c2); end; inc(c1); end;
inc(global); until global = 900000;
if find then writeln(a) else writeln('No found !'); writeln('klem1:: Time = ', gettickcount() - T);
T := GetTickCount();
global := 0;
repeat for p := 1 to maxint do if (p mod 3 = i) and (p mod 5 = j) and (p mod 7 = k) then break;