Две проги. Порезка труб и движения коня по шахматной доске. По какому принципу работают такие проги? - Общие вопросы C/C++

sadf · 03.03.2010, 20:46

Здравствуйте форумчане!
Есть две задачи, принцип работы которых мне не известен.
Помогите пожалуйста советом, по какому принципу работают такие проги.

1. Программа для порезки труб.
Есть заготовки труб, длиной "а". Необходимо написать прогу, в которую вводятся значения:
- Длина заготовок "а"
- количество типов труб, которые нужно получить в результате.
- длина труб первого типа.
- количество труб первого типа.
- длина труб второго типа.
- кол-во труб второго типа.
- .....
Прога должна посчитать как порезать заготовки на трубы, чтобы при этом использовать минимум заготовок. И вывести на экран на какие части будет резаться каждая заготовка и какой остаток будет оставаться от каждой заготовки.

2. Шахматы.
Написать прогу, которая пройдет конем по всей шахматной доске, пройдя по каждой клеточке всего один раз и в конце вернется на исходное положение.

pu4koff · 03.03.2010, 22:26

Ну тут либо математическую модель составлять и по ней всё рассчитывать. Либо реализовывать генетический алгоритм и полагаться на везение

k1r1ch · 04.03.2010, 15:13

Первая задача, возможно, решается принципом динамического программирования, но проще перебором. Вторую скорее всего тоже динамикой...

Руслантус · 04.03.2010, 16:56

2-я задача решается методом перебора с отходом назад.

sadf · 06.03.2010, 20:04

Огромное спасибо за ответы!
Насчет первой уже понял, как её решать.

А насчет второй... Что такое "метод перебора с отходом назад" ?

03.03.2010, 20:46	#1
sadf Регистрация: 03.03.2010 Сообщений: 7	Две проги. Порезка труб и движения коня по шахматной доске. По какому принципу работают такие проги? Здравствуйте форумчане! Есть две задачи, принцип работы которых мне не известен. Помогите пожалуйста советом, по какому принципу работают такие проги. 1. Программа для порезки труб. Есть заготовки труб, длиной "а". Необходимо написать прогу, в которую вводятся значения: - Длина заготовок "а" - количество типов труб, которые нужно получить в результате. - длина труб первого типа. - количество труб первого типа. - длина труб второго типа. - кол-во труб второго типа. - ..... Прога должна посчитать как порезать заготовки на трубы, чтобы при этом использовать минимум заготовок. И вывести на экран на какие части будет резаться каждая заготовка и какой остаток будет оставаться от каждой заготовки. 2. Шахматы. Написать прогу, которая пройдет конем по всей шахматной доске, пройдя по каждой клеточке всего один раз и в конце вернется на исходное положение.

03.03.2010, 22:26	#2
pu4koff Старожил Регистрация: 22.05.2007 Сообщений: 9,065	Ну тут либо математическую модель составлять и по ней всё рассчитывать. Либо реализовывать генетический алгоритм и полагаться на везение http://coub.com/view/2hhtg

04.03.2010, 16:56	#4
Руслантус Наркоман самоучка Форумчанин Регистрация: 22.07.2007 Сообщений: 276	2-я задача решается методом перебора с отходом назад. #include <мозг.h>

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
монетки на шахматной доске!	grimm_jow	Общие вопросы C/C++	2	31.01.2010 10:27
Поиск пути на шахматной доске ходом ферзя	A!eI{S@nDrA	Помощь студентам	2	16.06.2009 09:51
На другом компе проги не работают	Ozerich	Общие вопросы C/C++	15	04.01.2009 01:09
По какому принципу решать ?	Artimbulidor	Помощь студентам	10	20.10.2008 18:43
Помогите начинающему написать две проги	Alex1991	Общие вопросы Delphi	1	18.10.2008 18:50

04.03.2010, 15:13	#3
k1r1ch ACM! Форумчанин Регистрация: 19.06.2009 Сообщений: 382	Первая задача, возможно, решается принципом динамического программирования, но проще перебором. Вторую скорее всего тоже динамикой...

06.03.2010, 20:04	#5
sadf Регистрация: 03.03.2010 Сообщений: 7	Огромное спасибо за ответы! Насчет первой уже понял, как её решать. А насчет второй... Что такое "метод перебора с отходом назад" ?