Вместо того чтобы учить студентов первых-вторых курсов информатике, нам сунули в зубы *censored* учебник какого-то препода, в котором задачки не столько на знание Си, сколько на соответствие уровню умственного развития как минимум Шерлока Холмса или блин Цезаря и кто там самый умный был =\ Ладно, постараюсь всё обьяснить как можно более внятно. Задача: Тема: рекурсивный вызов функции. 11. Разместить на шахматной доске максимальное количество слонов и ладей так, чтобы они не находились друг у друга " под боем" . Прога должна вернуть количество ладей и слонов, которым удалось уместиться. Известно что: - Ладья, не имея ограничений, может передвигаться на любое расстояние по горизонтали и вертикали. - Слон ходит по диагонали на любое расстояние. Первое же препятствие в решении задачи: в какой последовательности ставить слонов и ладьи на доску, так чтобы они заняли всё пространство? По логике - прогоняем все клетки доски и ставим по очереди то ладью, то слона, так чтобы никто никого не мог сбить. Разделения на белых и чёрных тут нет. Вот что получается: Как видите, справа осталось полным полно клеток, куда можно поставить фигуры с сохранением условия. Как рекурсией обойти и те клетки тоже? =\ Либо надо поменять порядок вставки слонов и ладей, но ведь он вообще нигде не оговорён, как я могу придумывать его? Тогда это уже вообще идиотизм, я не Си изучаю, а шахматы И вот код, который я набросал: Code: #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); } мне кажется, надо вызывать функцию рекурсией, поочерёдно задавая её фигуру для вставки, отличную от предыдущей. Но главная проблема в том, что я не знаю как проверить оставшиеся клетки =\
11. Разместить на шахматной доске максимальное количество слонов и ладей так, чтобы они не находились друг у друга " под боем" . У тебя на картинке все ладьи под боем - или "под боем" не должны быть слоны с ладьями а друг с другом можно? Итог задачи это втиснуть как можно больше "каких нибудь фигур" ну т.е. например 18 слонов это более удачная позиция чем 10 слонов и 2 ладьи??? Или кол во слонов и ладей (ладьев ) должно быть одинаковым?
2 spider-intruder +1 я сам озадачен подобными вопросами. У меня на картинке ни один слон не может побить ни одну ладью и наоборот. Имхо, надо разместить как можно больше и тех и тех. fucking аффтар учебника *WALL*
Узнай точно имеет ли право (по условию) тура бить туру ? Или слон слона Если да тонапиздячб всю доску турами ИЛИ слонами и у ьтя будет ответ 64*0 Если нетто твой рисунок не верен так как тура бьет туру и ставить на 1 линии их нельзя Мне самому интересно - давай уточни условие и будем писать ))) (это вам не кавычки тулить )
Вот что еще заметил (ну это очевидно просто как вариант) Нельзя размешать 1 фигуру возле другой ближе чем на 2 клетки...ну... т.е. Так ставить нельзя: Для туры: Y-тура X- Слон xxx xxxxyxxx xxx Для слона: х х xxx xyx xxx х х Может сначала разбить поле (иатрицу на подматрицы) 3*3 и как то от этого плясать ФОРМАТИРОВАНИЕ СДОХЛО! В асю стукни 988686ШЕСТЬ
2spider-intruder естественно сумма фигур имеется ввиду, потому что не было введено понятия цены слона и ладьи. по теме - не вижу ничего сложного. сложность правда будет не просто оценить, потому что сразу сказать сколько вариантов лишних отметает одна фигура не ясно. с другой стороны тк задача расчитана на первокурсников все должно сводиться к "бездумному" перебору, вот примерный псевдокод: Code: 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 - слоны)
Я так понимаю что это лаботаторная 4 задание 10 ;-) Судя по всему речь идет о том что слоны могут бить слонов но не тур и наоборот. т.е. твоя картинка пока что верна. НУ ИМХО Конечно! http://forum.ixbt.com/topic.cgi?id=26:37553 - BlackLor (Pell) НЕ верно сказал! Так не делай. Твой ответ будет 8 слонов в первой строке и еше нсколько внизу!!! А у тебя надо посчитать максималку того и того... Надо мудрить с квадратами 3*3 кароче в асю )
2Zaco Я свой универ уже благо закончил N лет назад и уже 2 работы поменял Мне просто интересна задача >> "сложность правда будет не просто оценить, потому что сразу сказать сколько вариантов лишних отметает одна фигура не ясно" В том то и дело
Хде ж я узнаю более подробное условие? Он наверно уже помер. Надо довольствоваться текстом из учебника. Насколько я понимаю - там нет разделения на масти. И ладья ладью бить не может. Как можно делить на масти если у каждой стороны по настоящим правилам не может быть больше двух слонов и двух ладей? Я вот чо заметил - все слоны стоят на тёмных клетках, все ладьи - на белых. То что на скриншоте выше - в идеале всё должно ещё раз повториться и мы должны получить такой результат: хмммм я думаю надо попробовать тупо запускать функцию ещё раз, тогда она проставит два вторых столбца фигур, которых не хватает на первом скрине в первом посте. но тогда какая тут нахрен рекурсия, если функция будет брать с нуля? =\ мм надо запоминать максимальный Х и юзать его при вторичном и последующих (теоретически. так то они уже не понадобятся) проходах по доске.
y Не верно - у тя получается 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 а отмеченая красным ладья разве не делает шах слонам, которые стоят сразу после нее (влево) ?
Задача немного туповатая. Когда я решал подобные задачи, ответ был не тривиален и зависел, чаще всего, от размера шахматной доски NxN (где N - входной параметр в опр. интервале). Здесь же, как я понимаю, подразумевается размер реальной доски 8x8 => ответ у задачи всегда один и тот же. Решай на листочке, потом подсунь преподу что то вроде print res; // =)
2KEZ перечитай сообщение мое, я как раз и написал что никая не может бить никакую 2Joker-jar ну ясное дело, только тут и требуется какая-никакая оптимизация. и в условии написано, что функция должна быть рекурсивной, скорее всего тут и просят перебрать тебе не кажется? если делать прямым перебором, то наверное она будет долго решаться.