• Стоит задача - создать цепочку, в которой будут содержаться все числа от 0000 до 9999, причём длина этой цепочки должна быть минимальной. То есть например у нас есть цепочка из 40к символов - 000000010002...9999, нужно переставить цифры местами. По моим подсчётам длина цепочки минимальная равна 10003.
    Создал я программку, которая в массив из 40к ячеей закидывает все это. Теперь ,видимо, нужно в цикле смотреть все возможное переборы... но как это реализовать хз... Понятно, что цикл будет while(len(A))>10003:
    А что в самом цикле? как уменьшать длину строки? Если есть какие-то идеи, напишите пожалуйста. (Python/Pascal). Важен не сам код, а понимание того, что нужно делать

Ответы 5

  • Забавно, что это вообще сработало. Как вы поняли, достаточно просматривать возможные варианты i-того символа, начиная с (a[i-1] + 1) mod 10
  • Стоп
    • Автор:

      cutietic3
    • 6 лет назад
    • 0
  • Забавно. Я думал, что начинаю с a[i-1] + 1, а начинал с единицы. Но главное, что работает. Не знаю, почему
  • ОМГ, сейчас буду разбираться! Спасибо огромное!
  • {Если что, часть программы не нужна для построения цепочки. Она просто иллюстрирует, что полученный результат верен.}var sq : array[0..999] of array[0..9] of boolean; co : array[0..999] of integer; ar : array[1..10003] of 0..9;  i,j: integer; x: integer; t : boolean; begin for i := 0 to 999 do   begin   for j := 0 to 9 do   sq[i][j] := false;   co[i] := 0;   end; for i := 1 to 3 do   ar[i] := 0; i := 3; t := true; {write('000');} while t do   begin   i := i + 1;   x := ar[i-3]*100 + ar[i-2]*10 + ar[i-1];   if co[x] >= 10 then t := false     else     begin     j := 1;     while sq[x][j] do        j := (j + 1) mod 10;     ar[i] := j;     sq[x][j] := true;     co[x] := co[x] + 1;     {write(j)}     end;   end; {writeln;} writeln('Length: ',i - 1); {просто чтобы убедиться} for i := 0 to 999 do   for j := 0 to 9 do   sq[i][j] := false;  t := true; j := 0; i := 1; while (i <= 10000) and t do   begin   x := ar[i] * 100 + ar[i+1] * 10 + ar[i+2];   if sq[x][ar[i+3]] then t := false     else     begin     sq[x][ar[i+3]] := true;     j := j + 1;     end;   i := i + 1   end; if t and (j = 10000) then   write('Confirmed')end.
    • Автор:

      kaseygmoi
    • 6 лет назад
    • 0
  • Добавить свой ответ

Войти через Google

или

Забыли пароль?

У меня нет аккаунта, я хочу Зарегистрироваться

How much to ban the user?
1 hour 1 day 100 years