Версия для печати темы

Автор: Sofo4ka 24.10.2006 23:14

задуманно натуральное число х.известны три числа- остатки от деления этого числа 3,5,7 - i,j,k соответсвенно. найти Х

Автор: klem4 25.10.2006 1:57

а что непонятного ?

X mod 3 = a
X mod 5 = b
X mod 7 = c

a, b, c - известны

Задача кстати решалась, можно поискать.

Автор: Гость 25.10.2006 2:06

х=3l*i
x=5m*j
x=7t*k


потом типа 3l*i=5m*j

так объяснили

Автор: volvo 25.10.2006 2:18

Sofo4ka, простым перебором чисел находишь те, что удовлетворяют заданным условиям. Этого тебе вполне хватит (все официальные решения с олимпиад этой задачи основывались именно на переборе - проблем ни у кого не возникло...)

Автор: Sofo4ka 25.10.2006 17:44

а у мя возникла )

Автор: volvo 25.10.2006 17:48

В чем именно?

Запустить цикл от 1 до 32767 (максимально возможное число для Integer), и для каждого числа проверять равенство остатков от его деления на 3, 5, 7 числам i, j, k соответственно?

Автор: klem4 25.10.2006 18:10

Вот что я придумал :

uses crt;
var
  i, j, k: Integer;
  c1, c2, c3, a, b, c: Integer;
  find: boolean;

begin
  clrscr;

  write('i = '); readln(i);
  write('j = '); readln(j);
  write('k = '); readln(k);

  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;


  if find then writeln(a)
   else writeln('No found !');

  readln;
end.

Вот только будет ли это быстрее обычного перебора

Автор: klem4 25.10.2006 18: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 18:56

Потому, что некорректно Ты же не инициализируешь Find и C1 заново при каждой итерации, следовательно, у тебя в первом случае показывается время одной итерации, а во втором - время ВСЕХ... Вот так - корректнее:

uses windows, crt;
var
  i, j, k: Integer;
  c1, c2, c3, a, b, c,
  p, global: Integer;
  find: boolean;

  T: dword;

begin
  clrscr;

  write('i = '); readln(i);
  write('j = '); readln(j);
  write('k = '); readln(k);

  T := gettickcount();


  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;

    inc(global);
  until (global = 900000);

  writeln('Result = ', p);
  writeln('klem2:: Time = ', gettickcount() - T);


  readln;
end.

Эскизы прикрепленных изображений

Автор: klem4 25.10.2006 19:00

LOL ))))

Спасибо )))

Sofo4ka, используй простой перебор

Автор: Michael_Rybak 25.10.2006 19:26

Только перебирать надо не до 32767, а до 3*5*7.

Если a == b (mod 3), то (a-b) == 0 (mod 3)
Если a == b (mod 5), то (a-b) == 0 (mod 5)
Если a == b (mod 7), то (a-b) == 0 (mod 7)

А если (a-b) == 0 (mod 3, 5 и 7), то (a-b) == 0 mod (3 * 5 * 7).

Поэтому, найдя первый ответ X, надо выводить по очереди все числа вида X + 105 * K, и только их.