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

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


Знаток
****

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

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


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

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


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


Знаток
****

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

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


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



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


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

Группа: Пользователи
Сообщений: 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 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


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

 





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