Форум программистов, компьютерный форум CyberForum.ru

Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. - C++

Восстановить пароль Регистрация
 
Хулиган
 Аватар для Хулиган
85 / 80 / 12
Регистрация: 08.08.2012
Сообщений: 737
24.01.2013, 20:58     Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. #1
Добрый вечер!\
путешествовал по форуму и нашёл такую задачку....кто сможет решить отпишитесь!

Имеется n винтов и n гнезд, расположенных в произвольном порядке. Каждому винту соответствует по диаметру только одно гнездо. Все винты имеют разные диаметры.

Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. В результате такой операции можно выяснить: (1) винт тоньще гнезда - не подходит, (2) винт толще гнезда - не подходит, (3) или винт точно входит в гнездо - подходит.

Сравнивать винты или гнезда между собой нельзя.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.01.2013, 20:58     Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j.
Посмотрите здесь:

C++ Просто расставить комменты, прога очень маленькая) Только сегодня , пожалуйста
C++ Дан текст на русском языке. Напечатать в алфавитном порядке все согласные буквы,которые входят только в одно слово
Массив: В массиве из 20 элементов расставить по возрастанию только четные C++
C++ Работает,правда,в одно действие
C++ выдает только одно решение
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
24.01.2013, 21:06     Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. #2
Только перебор, ведь винты и гнезды в произвольном порядке, который даже сортировать нельзя :/
Перебор: берем первый винт и идем по массиву гнезд до тех пор, пока не вставится. Берем второй винт, идем по массиву гнезд.. и так далее. Проверку на то, что гнездо занято можно опустить, ведь все гнезды и винты разные.
Хулиган
 Аватар для Хулиган
85 / 80 / 12
Регистрация: 08.08.2012
Сообщений: 737
24.01.2013, 21:20  [ТС]     Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. #3
аааа....не такая она уж и интересная оказалась(( я подумал, что можно только 1 раз 1 винт всунуть в гнездо! не правильно понял условие
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
24.01.2013, 21:33     Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. #4
Можно и поинтереснее решить.
Берем первый болт и проходим все гнезда. Запоминаем, какие выдали больше, какие меньше и в какое он подходит.
Берем второй болт и проверяем его на том гнезде, в которое подошел первый. Если он меньше этого гнезда, то имеет смысл проходить только те гнезда, которые на первом шаге были меньше первого болта. И т.д.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
25.01.2013, 06:47     Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. #5
I.M., и правда.. Ну вот, мне теперь перед человеком и собой стыдно :/
Yandex
Объявления
25.01.2013, 06:47     Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j.
Ответ Создать тему
Опции темы

Текущее время: 12:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru