IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> надо написать Идея описания решение, и я не очень понял саму задачку
сообщение
Сообщение #1


Знаток
****

Группа: Пользователи
Сообщений: 324
Пол: Мужской
Реальное имя: maksim

Репутация: -  1  +


Задачка
Дано 100 карточек выложенные в строку. На каждой карточке написано по одной цифре. Можно или нельзя выложить так карточки чтобы не одно число не было на том же самом месте? Надо найдите хотя бы один вариант расположения карточек.
Напишите решения идеи описание.
Объясните задачку и как пишется эта идея. Или тут надо алгоритм написать? И еще будит ли перестановка засчитана если поменяем два одинаковых числа местами?

Моя идея
Проверить на одинаковые цифры рядом и их переместить одну на -1 позицию и потом заного проверить если есть еще такие числа и потом все числа сдвинуть влево на одну позицию.


--------------------
Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Типа того.
Будет нагляднее, если исходный массив отсортирован так: все одинаковые числа идут подряд, длины групп убывают.
Например:
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))
Может, есть оптимальнее.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Рекурсия? smile.gif
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: спрашивай, что неясно.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Знаток
****

Группа: Пользователи
Сообщений: 324
Пол: Мужской
Реальное имя: maksim

Репутация: -  1  +


Надо только идею описания решения мне написать. Если идея должна быть программой то наверное без разницы рекурсия или нет.
А тут на сколько увеличивается и что Inc(Cards[Ini[i]]); . Я знаю что Inc увеличивает число если незадано то на один если задано то на столько сколько задано.



--------------------
Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(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 .


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Знаток
****

Группа: Пользователи
Сообщений: 324
Пол: Мужской
Реальное имя: maksim

Репутация: -  1  +


Цитата(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 -


--------------------
Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(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 получаются общие количества каждой цифры поэлементно.
Стало понятнее?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Знаток
****

Группа: Пользователи
Сообщений: 324
Пол: Мужской
Реальное имя: maksim

Репутация: -  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]);

ну и так далее а где 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 и так большей если есть как то так странно я вы до этого недодумалсябы

Сообщение отредактировано: maksimla -


--------------------
Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Знаток
****

Группа: Пользователи
Сообщений: 324
Пол: Мужской
Реальное имя: maksim

Репутация: -  1  +


Как идею решение надо написать программу или алгоритм им предоставить или объяснить что сперва в массив все числа потом создаем второй массив чисел от 0 до 9 и записываем сколько этих есть чисел всего то есть сколько нулей единиц и так далее потом сравниваем первый со вторым массивом если в первом другое число стоит то записываем в третий массив то число которое во втором стоит и со второго массива убираем это число. Так как надо эту идею описать им?


--------------------
Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(maksimla @ 10.10.2009 15:10) *
как то так странно я вы до этого недодумалсябы
Это довольно стандартный прием. Побольше опыта - додумаешься и не до такого smile.gif.

Цитата(maksimla @ 10.10.2009 20:01) *
Как идею решение надо написать программу или алгоритм им предоставить или объяснить что сперва в массив все числа потом создаем второй массив чисел от 0 до 9 и записываем сколько этих есть чисел всего то есть сколько нулей единиц и так далее потом сравниваем первый со вторым массивом если в первом другое число стоит то записываем в третий массив то число которое во втором стоит и со второго массива убираем это число. Так как надо эту идею описать им?
Да, сначала собираем все карточки, какие есть, в упорядоченный массив Cards. Затем конструируем новую строку по порядку так, чтобы карта в ней не совпадала с картой на той же позиции в данной строке. При этом берем карты из массива Cards, возвращая их на место потом в случае неудачи. Удачей считаем, когда мы доходим до последней позиции, всякий раз удовлетворив условию различия карт. То есть на каждом шагу, от первой до последней позиции, в массиве Cards находится карта, отличная от начальной. В случае неудачи повторяем перебор с предыдущей позиции, в случае удачи выводим сконструированную новую строку.

Добавлено через 4 мин.
Я все же перенесу тему в Алгоритмы. Теоретические вопросы - это вопросы по Паскалю. Например, тебя интересуют тонкости работы цикла for .. do .


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Знаток
****

Группа: Пользователи
Сообщений: 324
Пол: Мужской
Реальное имя: maksim

Репутация: -  1  +


ясно спасибо все понял я


--------------------
Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:41
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name