Задачка
Дано 100 карточек выложенные в строку. На каждой карточке написано по одной цифре. Можно или нельзя выложить так карточки чтобы не одно число не было на том же самом месте? Надо найдите хотя бы один вариант расположения карточек.
Напишите решения идеи описание.
Объясните задачку и как пишется эта идея. Или тут надо алгоритм написать? И еще будит ли перестановка засчитана если поменяем два одинаковых числа местами?
Моя идея
Проверить на одинаковые цифры рядом и их переместить одну на -1 позицию и потом заного проверить если есть еще такие числа и потом все числа сдвинуть влево на одну позицию.
Полная версия: надо написать Идея описания решение
Типа того.
Будет нагляднее, если исходный массив отсортирован так: все одинаковые числа идут подряд, длины групп убывают.
Например:
7 7 7 7 7 7 7 1 1 1 1 3 3 3 3 2 2 2 5
Если длина первой группы больше половины, то решения нету.
Иначе сдвигаем на длину первой группы:
3 3 3 2 2 2 5 7 7 7 7 7 7 7 1 1 1 1 3
Такой вариант будет работать за O(n*log(n))
Может, есть оптимальнее.
Будет нагляднее, если исходный массив отсортирован так: все одинаковые числа идут подряд, длины групп убывают.
Например:
7 7 7 7 7 7 7 1 1 1 1 3 3 3 3 2 2 2 5
Если длина первой группы больше половины, то решения нету.
Иначе сдвигаем на длину первой группы:
3 3 3 2 2 2 5 7 7 7 7 7 7 7 1 1 1 1 3
Такой вариант будет работать за O(n*log(n))
Может, есть оптимальнее.
Рекурсия? 
2 maksimla: спрашивай, что неясно.
const
n=100; {number of cards}
m=9; {maximum digit used, starting with 0}
type
tLayout= array[1..n]of byte;
var
Ini,Res: tLayout;
Cards: array[0..m]of integer;
function Arrange(k: integer): boolean;
var
i: byte;
f: boolean;
begin
f:= false;
i:= 0;
repeat
if (i<>Ini[k])and(Cards[i]>0) then begin
Res[k]:=i;
Dec(Cards[i]);
f:=(k=n)or Arrange(k+1);
Inc(Cards[i]);
end;
Inc(i)
until f or(i>m);
Arrange:= f
end;
var
i: integer;
begin
for i:= 1 to n do Ini[i]:= Random(m+1);
for i:= 1 to n do Write(Ini[i],' ');
WriteLn;
for i:= 0 to m do Cards[i]:= 0;
for i:= 1 to n do Inc(Cards[Ini[i]]);
if Arrange(1) then for i:= 1 to n do Write(Res[i],' ') else Write('No way');
WriteLn;
ReadLn
end.
2 maksimla: спрашивай, что неясно.
Надо только идею описания решения мне написать. Если идея должна быть программой то наверное без разницы рекурсия или нет.
А тут на сколько увеличивается и что Inc(Cards[Ini[i]]); . Я знаю что Inc увеличивает число если незадано то на один если задано то на столько сколько задано.
А тут на сколько увеличивается и что Inc(Cards[Ini[i]]); . Я знаю что Inc увеличивает число если незадано то на один если задано то на столько сколько задано.
Цитата(maksimla @ 10.10.2009 10:43) 
А тут на сколько увеличивается и что Inc(Cards[Ini[i]]); . Я знаю что Inc увеличивает число если незадано то на один если задано то на столько сколько задано.
Правильно. Именно это тут и делается. В этой строчке мы вычисляем, сколько карточек каждого вида у нас есть. Например, если данная строка карточек выглядит так (используем цифры от 0 до 5):2 4 3 3 2 0 2 5 0
- то массив Cards получится (после работы этой строки) таким:
2 0 3 2 1 1
Это значит, что у нас есть 2 нуля, ноль единиц, 3 двойки, 2 тройки, 1 четверка и 1 пятерка. Этот массив мы будем использовать при переборе различных комбинаций.
Идея решения состоит, по сути, в переборе всех возможных комбинаций выкладывания имеющихся карточек в строку. Функция Arrange(k) кладет в цикле на k-тое место одну из имеющихся у нас в запасе карт - причем, не совпадающую с той, которая лежит на этом месте в исходной строке (массив Ini). Эту карту она записывает в массив Res и удаляет из массива Cards. Далее происходит рекурсивный вызов этой же процедуры, но уже для позиции k+1. Если же положить отличную от начальной карту невозможно (в массиве Cards кончились карты, отличные от начальной) - происходит выход из функции без дальнейшего рассмотрения, при этом она возвращает значение FALSE. Если же нам удалось дойти до самой последней позиции и положить на нее правильную карту (то есть не совпадающую с начальной), то функция возвращает значение TRUE. По этому признаку дальнейший поиск прекращается, и мы выдаем на печать массив Res, который содержит искомую комбинацию. Если дойти до последней карты так и не удалось, то выводится фраза "No way" (невозможно).
Поскольку фактически происходит полный перебор, то результат гарантирован.
Понятно - или еще поподробнее объяснить?
Совет: задай входные параметры поменьше (типа n=5, m=3) и поиграй с ними. Очень полезно походить шагами кнопкой F7, наблюдая все переменные: Res, Cards, f, i .
Цитата(Lapp @ 10.10.2009 10:28)
Например, если данная строка карточек выглядит так (используем цифры от 0 до 5):
2 4 3 3 2 0 2 5 0
- то массив Cards получится (после работы этой строки) таким:
2 0 3 2 1 1
Это значит, что у нас есть 2 нуля, ноль единиц, 3 двойки, 2 тройки, 1 четверка и 1 пятерка. Этот массив мы будем использовать при переборе различных комбинаций.
мне всё ровно не доходит как так получилось из этого Inc(Cards[Ini[i]]); все числа 2 0 3 2 1 1 можете объяснить ?
а так если смотреть то дальше идет так
Arrange(1) обращаемся к функции
Код
k:=1
i:=0
if (0<>2)and(2>0) then begin
Res[k]:=0;
Dec(Cards[i]); 1 0 3 2 11
f:=(k=n)or Arrange(k+1); k:=2
if (0<>4)and(1>0) then begin
Res[k]:=0;
Dec(Cards[i]); 0 0 3 2 11
f:=(k=n)or Arrange(k+1); k:=3
if (0<>3)and(0>0) then begin
inc(i) i=1
if (1<>3)and(0>0) then begin
inc(i) i=2
if (2<>3)and(3>0) then begin
Res[k]:=2;
Dec(Cards[i]); 0 0 2 2 11
f:=(k=n)or Arrange(k+1); k:=4
if (0<>3)and(0>0) then begin
inc(i) i=1
if (1<>3)and(0>0) then begin
inc(i) i=2
if (2<>3)and(2>0) then begin
Res[k]:=2;
Dec(Cards[i]); 0 0 1 2 1 1
f:=(k=n)or Arrange(k+1); k:=5
if (0<>2)and(0>0) then begin
inc(i) i=1
if (1<>2)and(0>0) then begin
inc(i) i=2
if (2<>2)and(1>0) then begin
inc(i) i=3
if (3<>2)and(2>0) then begin
Res[k]:=3;
Dec(Cards[i]); 0 0 1 1 1 1
f:=(k=n)or Arrange(k+1); k:=6
if (0<>0)and(0>0) then begin
inc(i) i=1
if (1<>0)and(0>0) then begin
inc(i) i=2
if (2<>0)and(1>0) then begin
Res[k]:=2;
Dec(Cards[i]); 0 0 0 1 1 1
f:=(k=n)or Arrange(k+1); k:=7
if (0<>2)and(0>0) then begin
inc(i) i=1
if (1<>2)and(0>0) then begin
inc(i) i=2
if (2<>2)and(0>0) then begin
inc(i) i=3
if (3<>2)and(1>0) then begin
Res[k]:=3;
Dec(Cards[i]); 0 0 0 0 1 1
f:=(k=n)or Arrange(k+1); k:=8
if (0<>5)and(0>0) then begin
inc(i) i=1
if (1<>5)and(0>0) then begin
inc(i) i=2
if (2<>5)and(0>0) then begin
inc(i) i=3
if (3<>5)and(0>0) then begin
inc(i) i=4
if (4<>5)and(1>0) then begin
Res[k]:=4;
Dec(Cards[i]); 0 0 0 0 0 1
f:=(k=n)or Arrange(k+1); k:=9;
сейчас все будут гнать к i:=5 и тогда
if (5<>0)and(1>0) then begin
Res[k]:=5;
Dec(Cards[i]); 0 0 0 0 0 0
f:=(9=9);
Inc(Cards[i]) 0 0 0 0 0 1 вот это не очень понел я
until f or(i>m);
Arrange:= f
и все конец
запишут наверное так
0 0 2 2 3 2 3 4 5
Inc(Cards[i]) я вот этого не понял
и как еще этот текст скрыть
Цитата(maksimla @ 10.10.2009 13:34)
мне всё ровно не доходит как так получилось из этого Inc(Cards[Ini[i]]); все числа 2 0 3 2 1 1 можете объяснить ?
Конечно, пожалуйста.Я повторю тут исходную строку:
2 4 3 3 2 0 2 5 0
Сколько в ней нулей? Два. Значит, Cards[0] должно быть равно 2.
Сколько в ней единиц? Ноль, то есть их нет. Значит, Cards[1] должно быть равно 0.
Сколько в ней двоек? Три. Значит, Cards[2] должно быть равно 3.
Сколько в ней троек? Две. Значит, Cards[3] должно быть равно 2.
Сколько в ней четверок? Одна. Значит, Cards[4] должно быть равно 1.
Сколько в ней пятерок? Одна. Значит, Cards[5] должно быть равно 1.
Таким образом, мы получаем, что массив Cards должен быть таким:
2 0 3 2 1 1
Теперь разберемся, как это осуществить в программе. Я процитирую строку из программы:
for i:= 1 to n do Inc(Cards[Ini[i]]);
В этом цикле мы проходим по всей входной строке и при каждой втрече цифры увеличиваем нужный элемент массива Cards. Таким образом, в массиве Cards получаются общие количества каждой цифры поэлементно.
Стало понятнее?
все ровно не очень понятно я так понимаю так
берем этот массив
2 4 3 3 2 0 2 5 0
и строчку
и получается у меня так
ну и так далее а где 1+1 не вижу или не понел и как если потом выводить
должно 0 выводить постоянно но так не выводит не понимаю
но
for i:= 0 to m do Cards[i]:= 0; тут 0 и поэтому
for i:= 1 to n do Inc(Cards[Ini[i]]); тут как то выходит что нетолько так
i:=3;
ini[3];
cards[3];
inc(cards[4]);
i:=4;
ini[3];
cards[3];
inc(cards[4]);
но еще изменяемся с 0 на 1 и так большей если есть как то так странно я вы до этого недодумалсябы
берем этот массив
2 4 3 3 2 0 2 5 0
и строчку
for i:= 1 to n do Inc(Cards[Ini[i]]);
и получается у меня так
Код
i:=1
ini[i]:=2;
cards[2];
inc(cards[3]);
i:=2;
ini[i];=4;
cards[4];
inc(cards[5]);
i:=3;
ini[3];
cards[3];
inc(cards[4]);
i:=4;
ini[3];
cards[3];
inc(cards[4]);
ini[i]:=2;
cards[2];
inc(cards[3]);
i:=2;
ini[i];=4;
cards[4];
inc(cards[5]);
i:=3;
ini[3];
cards[3];
inc(cards[4]);
i:=4;
ini[3];
cards[3];
inc(cards[4]);
ну и так далее а где 1+1 не вижу или не понел и как если потом выводить
for i:= 0 to m do write(Cards[i],' '); writeln;
должно 0 выводить постоянно но так не выводит не понимаю
но
for i:= 0 to m do Cards[i]:= 0; тут 0 и поэтому
for i:= 1 to n do Inc(Cards[Ini[i]]); тут как то выходит что нетолько так
i:=3;
ini[3];
cards[3];
inc(cards[4]);
i:=4;
ini[3];
cards[3];
inc(cards[4]);
но еще изменяемся с 0 на 1 и так большей если есть как то так странно я вы до этого недодумалсябы
Как идею решение надо написать программу или алгоритм им предоставить или объяснить что сперва в массив все числа потом создаем второй массив чисел от 0 до 9 и записываем сколько этих есть чисел всего то есть сколько нулей единиц и так далее потом сравниваем первый со вторым массивом если в первом другое число стоит то записываем в третий массив то число которое во втором стоит и со второго массива убираем это число. Так как надо эту идею описать им?
Цитата(maksimla @ 10.10.2009 15:10)
как то так странно я вы до этого недодумалсябы
Это довольно стандартный прием. Побольше опыта - додумаешься и не до такого .Цитата(maksimla @ 10.10.2009 20:01)
Как идею решение надо написать программу или алгоритм им предоставить или объяснить что сперва в массив все числа потом создаем второй массив чисел от 0 до 9 и записываем сколько этих есть чисел всего то есть сколько нулей единиц и так далее потом сравниваем первый со вторым массивом если в первом другое число стоит то записываем в третий массив то число которое во втором стоит и со второго массива убираем это число. Так как надо эту идею описать им?
Да, сначала собираем все карточки, какие есть, в упорядоченный массив Cards. Затем конструируем новую строку по порядку так, чтобы карта в ней не совпадала с картой на той же позиции в данной строке. При этом берем карты из массива Cards, возвращая их на место потом в случае неудачи. Удачей считаем, когда мы доходим до последней позиции, всякий раз удовлетворив условию различия карт. То есть на каждом шагу, от первой до последней позиции, в массиве Cards находится карта, отличная от начальной. В случае неудачи повторяем перебор с предыдущей позиции, в случае удачи выводим сконструированную новую строку.Добавлено через 4 мин.
Я все же перенесу тему в Алгоритмы. Теоретические вопросы - это вопросы по Паскалю. Например, тебя интересуют тонкости работы цикла for .. do .
ясно спасибо все понял я
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.