Просмотр полной версии : Задачка-головоломка
Вместо того чтобы учить студентов первых-вторых курсов информатике, нам сунули в зубы *censored* учебник какого-то препода, в котором задачки не столько на знание Си, сколько на соответствие уровню умственного развития как минимум Шерлока Холмса или блин Цезаря и кто там самый умный был =\
Ладно, постараюсь всё обьяснить как можно более внятно.
Задача:
Тема: рекурсивный вызов функции.
11. Разместить на шахматной доске максимальное количество слонов и ладей так,
чтобы они не находились друг у друга " под боем" .
Прога должна вернуть количество ладей и слонов, которым удалось уместиться.
Известно что:
- Ладья, не имея ограничений, может передвигаться на любое расстояние по горизонтали и вертикали.
- Слон ходит по диагонали на любое расстояние.
Первое же препятствие в решении задачи: в какой последовательности ставить слонов и ладьи на доску, так чтобы они заняли всё пространство?
По логике - прогоняем все клетки доски и ставим по очереди то ладью, то слона, так чтобы никто никого не мог сбить. Разделения на белых и чёрных тут нет.
Вот что получается:
http://img148.imageshack.us/img148/7275/var1oe1.jpg
Как видите, справа осталось полным полно клеток, куда можно поставить фигуры с сохранением условия.
Как рекурсией обойти и те клетки тоже? =\
Либо надо поменять порядок вставки слонов и ладей, но ведь он вообще нигде не оговорён, как я могу придумывать его? Тогда это уже вообще идиотизм, я не Си изучаю, а шахматы :mad:
И вот код, который я набросал:
#include <stdio.h>
void count(int x, int y, char model, int doska[8][8]){
for(int i=0; i<8; i++)
for(int j=0; j<8; j++)
if(doska[i][j] == 1)
printf("shit");
};
void main(){
int doska[8][8] = {0};
doska[2][3] = 1;
int ladja = 0;
int slon = 0;
int x = 0;
int y = 0;
char model = 'l'; // l = ladja, s = slon
printf("\nBefore counting: \n\n");
for(int i=0; i<8; i++)
for(int j=0; j<8; j++){
if(j==0)
printf("\n");
printf("%d ", doska[i][j]);
}
printf("\n\n");
// start function
count(0,0,model, doska);
// end function
printf("\n---------------------------------------\nAfter counting: \n\n");
for(i=0; i<8; i++)
for(int j=0; j<8; j++){
if(j==0)
printf("\n");
printf("%d ", doska[i][j]);
}
printf("\n\nLadja: %d\nSlon: %d\n\n", ladja, slon);
}
мне кажется, надо вызывать функцию рекурсией, поочерёдно задавая её фигуру для вставки, отличную от предыдущей.
Но главная проблема в том, что я не знаю как проверить оставшиеся клетки =\
Вместо того чтобы учить студентов первых-вторых курсов информатике, нам сунули в зубы *censored* учебник какого-то препода, в котором задачки не столько на знание Си, сколько на соответствие уровню умственного развития как минимум Шерлока Холмса или блин Цезаря и кто там самый умный был =\
ИМХО хороший программист - программист с хорошим нестандартным мышлением.
2 Ci5
согласен :( тока вот задачу надо решить к зимней сессии
spider-intruder
28.11.2007, 13:00
11. Разместить на шахматной доске максимальное количество слонов и ладей так,
чтобы они не находились друг у друга " под боем" .
У тебя на картинке все ладьи под боем - или "под боем" не должны быть слоны с ладьями а друг с другом можно?
Итог задачи это втиснуть как можно больше "каких нибудь фигур" ну т.е. например 18 слонов это более удачная позиция чем 10 слонов и 2 ладьи???
Или кол во слонов и ладей (ладьев :-)) должно быть одинаковым?
2 spider-intruder
+1 :) я сам озадачен подобными вопросами.
У меня на картинке ни один слон не может побить ни одну ладью и наоборот.
Имхо, надо разместить как можно больше и тех и тех.
fucking аффтар учебника *WALL*
spider-intruder
28.11.2007, 13:30
Узнай точно имеет ли право (по условию) тура бить туру ? Или слон слона
Если да тонапиздячб всю доску турами ИЛИ слонами и у ьтя будет ответ 64*0
Если нетто твой рисунок не верен так как тура бьет туру и ставить на 1 линии их нельзя
Мне самому интересно - давай уточни условие и будем писать )))
(это вам не кавычки тулить ;))
spider-intruder
28.11.2007, 13:37
Вот что еще заметил (ну это очевидно просто как вариант)
Нельзя размешать 1 фигуру возле другой ближе чем на 2 клетки...ну... т.е.
Так ставить нельзя:
Для туры: Y-тура X- Слон
xxx
xxxxyxxx
xxx
Для слона:
х х
xxx
xyx
xxx
х х
Может сначала разбить поле (иатрицу на подматрицы) 3*3 и как то от этого плясать
ФОРМАТИРОВАНИЕ СДОХЛО! В асю стукни 988686ШЕСТЬ
2spider-intruder естественно сумма фигур имеется ввиду, потому что не было введено понятия цены слона и ладьи.
по теме - не вижу ничего сложного. сложность правда будет не просто оценить, потому что сразу сказать сколько вариантов лишних отметает одна фигура не ясно. с другой стороны тк задача расчитана на первокурсников все должно сводиться к "бездумному" перебору, вот примерный псевдокод:
int pole[8][8];
int pole_temp[8][8];
...
int sum(int num)
{
int i,j;
int max=0;
//bool ok=false;
for(i=0;i<8;i++)
for(j=0;j<8;j++)
if(pole[i][j]==0)
{
ok=true;
memcpy(&pole_temp[0][0], &pole[0][0], sizeof(pole));
put(i,j,type);
int s1=sum(num+1);
memcpy(&pole[0][0], &pole_temp[0][0], sizeof(pole));
put(i,j,Obratnyi(type)));
int s2=sum(num+1);
memcpy(&pole[0][0], &pole_temp[0][0], sizeof(pole));
if(s2>s1) s1=s2;
if(max<s1) max=s1;
}
//if(!ok) return 0;
return num+max;
}
...
sum(0);
--
put - ставим фигуру и обозначаем клетки, что под "боем", например -1. Obratnyi - если слон, то ладья и наоборот.
--
2spider-intruder :) это первый курс, не думайте что от вашего "колледжа" или чего там, от вас потребуют сильных мозгов. и еще, можно ставить ближе чем на две клетки, пример:
*SSSSSSS
********
********
********
********
********
********
*SSSSSSS
S - слоны)
spider-intruder
28.11.2007, 13:55
Я так понимаю что это лаботаторная 4 задание 10 ;-)
Судя по всему речь идет о том что слоны могут бить слонов но не тур и наоборот. т.е. твоя картинка пока что верна. НУ ИМХО Конечно!
http://forum.ixbt.com/topic.cgi?id=26:37553 - BlackLor (Pell)
НЕ верно сказал! Так не делай.
Твой ответ будет 8 слонов в первой строке и еше нсколько внизу!!! А у тебя надо посчитать максималку того и того... Надо мудрить с квадратами 3*3 кароче в асю )
spider-intruder
28.11.2007, 14:05
2Zaco
Я свой универ уже благо закончил N лет назад и уже 2 работы поменял :-)
Мне просто интересна задача :)
>> "сложность правда будет не просто оценить, потому что сразу сказать сколько вариантов лишних отметает одна фигура не ясно"
В том то и дело :)
Хде ж я узнаю более подробное условие? Он наверно уже помер.
Надо довольствоваться текстом из учебника.
Насколько я понимаю - там нет разделения на масти. И ладья ладью бить не может.
Как можно делить на масти если у каждой стороны по настоящим правилам не может быть больше двух слонов и двух ладей?
Я вот чо заметил - все слоны стоят на тёмных клетках, все ладьи - на белых.
То что на скриншоте выше - в идеале всё должно ещё раз повториться и мы должны получить такой результат:
http://img136.imageshack.us/img136/1417/var1wu5.jpg
хмммм
я думаю надо попробовать тупо запускать функцию ещё раз, тогда она проставит два вторых столбца фигур, которых не хватает на первом скрине в первом посте.
но тогда какая тут нахрен рекурсия, если функция будет брать с нуля? =\
мм
надо запоминать максимальный Х и юзать его при вторичном и последующих (теоретически. так то они уже не понадобятся) проходах по доске.
spider-intruder
28.11.2007, 16:27
Не верно - у тя получается 8 тех и 8 тех
Я вот придумал как разместить 8 слонов и 9 тур
Думаю дальше )
спустя минуту:
Знаю как 10 слонов и 8 тур...
Надо сначала придумать максимально число тех и тех фигур а потом методом от обратного сочинить алгоритм.
Ты ж ХЭКИРЧеГ - у тя должно быть все по хитрому ;-)
http://img522.imageshack.us/img522/1230/var1oe1dj0.jpg
вот смотри
Omg %)
и никакой я не хэкерчег, йа веб-дизайнер! меня воротит от нулей и единиц, я не хочу быть системным программером и экономить каждый байт!
я письмо преподу написал, буду ждать ответа с подробностями.
2spider-intruder фигуры не должны бить друг друга, по-моему это в
условии написано. слон не может бить не только слона, но и ладью. хотя
конечно автор мог иметь вовсе что-то другое, тем не менее тогда можно
вообще ставить так:
*SSSSSSS
******L*
*****L**
****L***
***L****
**L*****
*L******
LSSSSSSS
но тогда смысл задачи ТЕРЯЕТСЯ - больше поставить никак нельзя, хотя бы
потому, что 14 - самое максимальное кол-во слонов которых можно
поставить тк 14 максимальное кол-во не пересекающихся диагоналей на
доске (диагонали не имеют права пересекаться тк их порождают сами
слоны), 8 - макисмальное кол-во ладей (очевидно), но тк любой вариант на
максимальную растоновку слонов будет съедать одну клетку диагонали, то
кол-во ладей 7. конечно, мы в общем случае никогда не имеет парва делать
общий максимум из максимума по слонам, однако в данной задаче если мы
возьмем не максимум, а например 13, то ладей можно будет поставить,
очевидно, лишь на одну больше (тк до этого было 7) => сумма общая не
меняется. при этом в задаче нас интересует общая сумма, тк не было
введено понятия цены одной фигуры по сравнению с другой - опять смысл
ТЕРЯЕТСЯ.
Ну вот, задача немного прояснилась:
> - все слоны одной масти?
Масть одна
> - в каком порядке надо ставить их на клетки? слон - ладья - слон?
Порядок не важен
> - вариант 10 ладей и 8 слонов (к примеру) приоритетнее чем 18 слонов?
В сумме должно быть максимальное количество, но хотя бы одна ладья и слон.
> Их должно быть по возможности одинаковое количество?
Нет.
>>В сумме должно быть максимальное количество, но хотя бы одна ладья и слон.
тогда 13, http://zaco.info/shah.cpp
*SSSSSSS
******L*
*****L**
****L***
***L****
**L*****
*L******
LSSSSSSS
а отмеченая красным ладья разве не делает шах слонам, которые стоят сразу после нее (влево) ?
Joker-jar
01.12.2007, 10:03
Задача немного туповатая. Когда я решал подобные задачи, ответ был не тривиален и зависел, чаще всего, от размера шахматной доски NxN (где N - входной параметр в опр. интервале). Здесь же, как я понимаю, подразумевается размер реальной доски 8x8 => ответ у задачи всегда один и тот же. Решай на листочке, потом подсунь преподу что то вроде
print res; // =)
Хм, довольно интересно, надо подумать! =/
2KEZ перечитай сообщение мое, я как раз и написал что никая не может бить никакую ;)
2Joker-jar ну ясное дело, только тут и требуется какая-никакая оптимизация. и в условии написано, что функция должна быть рекурсивной, скорее всего тут и просят перебрать тебе не кажется? если делать прямым перебором, то наверное она будет долго решаться.
;)
Joker-jar
01.12.2007, 16:45
Алгоритм решения задачи следующий. Доска - двумерный массив 8x8 байтов. Определяемся, например, так: 0 - клетка пуста, 1 - клетка занята слоном, 2 - клетка занята ладьей, 3 - клетка под боем слона, 4 - клетка под боем ладьи, 5 - клетка под боем обоих фигур. Далем две функции с входными параметрами - (доска, i, j), возвращающие также доску. Первая ставит на доску в клетку [i,j] слона а также забивает все клетки, в которые может срубить слон соотв. значениями (3, а если значение 2 - ладья бьет, то 5). Вторая делает то же самое, но для ладьи. Создается глобальная переменная, что-то вроде BestCount, в которую будет заноситься ответ. Теперь с рекурсией. Ее входные параметры: экземпляр доски, номер строки доски и count. В рекурсии идет цикл от 1 до 8 (идем по текущей строке доски). Если значение клетки = 0 (пусто) или 3 (под боем слона), то вызываем функцию вставки слона в эту клетку и вызываем рекрсию с параметрами: получившаяся доска, номер строки + 1, count + 1. Если значение клетки = 0 (пусто) или 2 (под боем ладьи), то вызываем функцию вставки ладьи в эту клетку и вызываем рекрсию с параметрами: получившаяся доска, номер строки + 1, count + 1. Вызов рекурсии происходит в цикле, без break'а. Если номер строки > 8 то если count > BestCount то BestCount := count и выход из рекурсии (это в самом начале функции).
после сообщения о тупости задачи не ожидал более тупого ответа, принимая во внимание то, что решение я привел.
Joker-jar
02.12.2007, 09:16
ZaCo, я говорил о тупости условия задачи. А то, что решение ты привел, эт не значит что оно единственное
ZaCo, перебор возможных комбинаций слонов и ладей можно реализовать в виде плагина к BruteNet ;)
2Joker-jar в смысле не единственное? ты привел, если и решение, то не той задачи. более того, твой алгоритм не решает даже проблемы связанной с твоим условием, не относящегося к этому топику.
podkashey
06.01.2008, 17:14
Какой тред нашел случайно... Прям в шоке..
ИМХО
X*******
**yyyyyy
*y*yyyyy
*yy*yyyy
*yyy*yyy
*yyyy*yy
*yyyyy*y
*yyyyyy*
Никто никого не бьет из друг друга, хотя бы по одному есть, кто есть кто насрать. Если нельзя чтобы вообще никто никого бил, то 8 на непересекающихся линиях. Хз че такая полемика... гы. Как запрограммировать незнаю - в фотошопе или пеинте ИМХО.
П.С. Ответ-то есть какой-нибудь уже?
podkashey, ты всмысле пытался нарисовать *** буквами "ХУЙ", или это реально решение...? )))))
в двух постах этой темы же написал, что тогда смысл у задачи теряется, точнее программистский. чем вам моя реализация-то (выводит даже !позиции! слонов и ладей) не нравится?:) хотя тут интересен исключительно момент оптимизации алгоритма..
Delimiter
07.01.2008, 05:54
От балды или фонаря наваял.... вдруг кто то посмотрит
char A[8][8];
CFile f;
CFileException e;
int step(int x,int y,int cnt)
{
int r1,r2,rm,i,j,k,l,e;
int ti,tj;
int vy1,vy2; //virtualnie koordinati
rm=cnt;
r2=r1=0;
for(i=x;i<8;i++)
{
for(j=y;j<8;j++)
{
if(A[i][j]==0)
{
// pitaemsia postavit ladiu
for(k=0,e=0;k<8 && e==0;k++)
{
if(A[i][k]>40 && k!=j)
e=1;
if(A[k][j]>40 && k!=i)
e=1;
}
if(e==0) // net figur pod boem
{
// stavim ladiu
A[i][j]='L';
// uvelichivaem schetchiki bitia
for(k=0;k<8;k++)
{
if(A[i][k]!='L')
A[i][k]++;
if(A[k][j]!='L')
A[k][j]++;
}
ti=i;tj=j;
r1=step(ti,tj,cnt+1); //uhodim v glubinu v 1-u diru
// vozvraschaem schetchiki
for(k=0;k<8;k++)
{
if(A[i][k]!='L')
A[i][k]--;
if(A[k][j]!='L')
A[k][j]--;
}
A[i][j]=0; // vozvraschaem kletke pervonachalnoe
}
// pitaemsia postavit slona
// virtualnie koordinati
vy1=i-j;
vy2=j+i;
for(k=0,e=0;k<8 && e==0;k++)
{
if(k!=j)
{
if(vy1+k>=0 && vy1+k<8)
{ // esli ne za ramkami
if(A[vy1+k][k]>40)
e=1;
}
if(vy2-k>=0 && vy2-k<8)
{
if(A[vy2-k][k]>40)
e=1;
}
}
}
if(e==0) // net figur pod boem
{
A[i][j]='S'; // stavim slona
//uvelichivaem schetchiki
for(k=0;k<8;k++)
{
if(k!=j)
{
if(vy1+k>=0 && vy1+k<8)
{
A[vy1+k][k]++;
}
if(vy2-k>=0 && vy2-k<8)
{
A[vy2-k][k]++;
}
}
}
ti=i;tj=j;
r2=step(ti,tj,cnt+1); //uhodim v glubinu vo 2-u diru
//umenshaem schetchiki
for(k=0;k<8;k++)
{
if(k!=j)
{
if(vy1+k>=0 && vy1+k<8)
{
A[vy1+k][k]--;
}
if(vy2-k>=0 && vy2-k<8)
{
A[vy2-k][k]--;
}
}
}
A[i][j]=0; // vozvraschaem kletke pervonachalnoe
}
if(r2>r1 && rm<r2)
rm=r2;
else
if(r1>r2 && rm<r1)
rm=r1;
}
}
y=0;
}
return rm;
}
void CZadach1Dlg::OnStart()
{
// TODO: Add your control notification handler code here
int i,j;
if(f.Open("c:\\rez.txt",CFile::modeCreate | CFile::modeWrite,&e))
f.Close();
for(i=0;i<8;i++)
for(j=0;j<8;j++)
A[i][j]=0;
m_rez=i=step(0,0,0);
UpdateData(false);
}
Delimiter
07.01.2008, 06:09
а если перед return rm вставить
// -------------- kusok dlia togo chtob glianut chto tam za rezultaty
if(rm==cnt)
{
if(cnt==14)
{
//vivod v file rezultatov predvaritelno poluchiv 14 kak rezultat
if(f.Open("c:\\rez.txt",CFile::modeWrite,(CFileException *)&e))
{
f.SeekToEnd();
for(i=0;i<8;i++)
{
f.Write("*---*---*---*---*---*---*---*---*\r\n|",36);
for(j=0;j<8;j++)
{
f.Write(" ",1);
if(A[i][j]>40)
{
f.Write((char *)&(A[i][j]),1);
}
else
{
f.Write(" ",1);
}
f.Write(" |",2);
}
f.Write("\r\n",2);
}
f.Write("*---*---*---*---*---*---*---*---*\r\n",35);
f.Close();
}
}
}
то все 14-ти значные результаты вывалятся в файл
vBulletin® v3.8.14, Copyright ©2000-2026, vBulletin Solutions, Inc. Перевод: zCarot