Форумы-->Форум для внеигровых тем-->
| Автор | C программисты |
|---|
есть в игре такие, готовые помочь?
помогите пожалуйста с 4мя задачами на зачет по проге
1)Обход доски конем
Написать программу, которая выводит обход доски заданного размера конем. Найти одно решение или указать, что решение невозможно.
2)Расстановка ферзей
Написать программу, которая расставляет на шахматной доске заданного размера ферзей так, чтобы они не били друг друга. Найти все решения или указать, что решение невозможно.
3) Задача о рюкзаке
По данному набору из n предметов стоимостями p1, p2, ..., pn и весами w1, w2, ..., wn найти поднабор (один предмет можно брать один раз) такой, что его стоимость будет максимальна среди всех поднаборов веса не более W.
4)Счастливые билеты
Для данного числа n=2k найти количество счастливых билетов, то есть тех, для которых сумма первых k цифр совпадает ссуммой последних k цифр.
Решать с помощью динамического программирования! простой перебор не прокатит(
за каждую задачу щедро отблагодарю) заранее спасибо) | | первые 2 задачи надо решать методом отката назад | | самые стандартные задачи на дин програмирование, погугли, код наверняка есть в инете | | Какова величина отката? | Другой способ решения задачи, состоит, очевидно, в переборе с отходом назад. Ниже дана иллюстрация подхода для доски 8x8.
Используем два одномерных массива row[64] и col[64] для хранения соответственно номеров строк и колонок, которые конь последовательно проходит по доске.
Конь, находящийся в позиции (i, j), может следующим ходом оказаться в клетках с координатами (i-2, j+1), (i-1, j+2), (i+1, j+2), (i+2, ,j+1), (i+2, ,j-1), (i+1, j-2), (i-1, j-2), (i-2, j-1). Заметим, что если конь находится вблизи края доски, то некоторые ходы могут вызвать перемещение коня за ее пределы, что, конечно же, недопустимо. Восемь возможных перемещений коня могут быть заданы в виде двух массивов ktmov1[] и ktmov2[], как продемонстрировано в следующем фрагменте программы.
Исходя из этого, конь, находящийся в позиции (i, j) может переместиться в позицию (i+ktmov[k], j+ktmov2[k]), где k - какое-либо значение из диапазона 0 - 7, выбираемое из условия, что конь должен остаться на доске. Итак, программа, реализующая перемещение коня в соответствии с вышеприведенными условиями будет выглядеть следующим образом:
int arr[8][8], row[64], col[64];
int ktmov1[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int ktmov2[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int i, j, move_num, d;
main() {
addknight( );
}
addknight( ) {
register int a, b, e;
/* пометить клетку как посещенную и запомнить координаты клетки */
arr[i][j] = 1;
row[move_num] = i;
col[move_num] = j;
move_num++;
/* проверить 8 возможных перемещений коня */
for ( a = 0 ; a <= 7 ; a++ ) {
/* если все ходы сделаны, печатаем их */
if ( move_num >= 64 ) {
writeboard( );
exit ( 0 );
}
/* определяем колонку и строку для следующего хода */
b = i + ktmov1[a];
e = j + ktmov2[a];
/* проверяем, что после выполенения хода конь остается на шахматной доске */
if ( b < 0 || b > 7 || e < 0 || e > 7 )
continue;
/* проверяем, были ли мы уже в этой клетке */
if ( arr[b][e] == 1 )
continue;
i = b; j = e;
addknight();
}
/* уменьшить счетчик ходов и попробовать сделать следующий ход */
move_num-- ;
/* освобождаем клетку, ранее занятую конем */
arr[row[move_num]][col[move_num]] = 0;
move_num--; /* пробуем сделать следующий ход */
i = row[move_num]; j = col[move_num];
move_num++;
}
writeboard( ) {
int a;
clrscr( );
gotoxy ( 1, 10 );
printf ( "Hit any key for next move " );
gotoxy ( 1, 11 );
for ( a = 0 ; a <= 63 ; a++ ) {
if ( a % 8 == 0 )
printf ( "\n" );
printf ( "#" );
}
for ( a = 0 ; a <= 63 ; a++ ) {
gotoxy ( col[a] * 3 + 1, 12 + row[a] );
printf ( "%3d", a + 1 );
getch( );
}
} | | тема закрыта by башня007 (2011-05-16 19:14:55) |
|---|
К списку тем
|
