Форум АНТИЧАТ

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)
-   С/С++, C#, Delphi, .NET, Asm (https://forum.antichat.xyz/forumdisplay.php?f=24)
-   -   Задачка-головоломка (https://forum.antichat.xyz/showthread.php?t=54607)

Дикс 28.11.2007 11:03
Задачка-головоломка
 
Вместо того чтобы учить студентов первых-вторых курсов информатике, нам сунули в зубы *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);


}
мне кажется, надо вызывать функцию рекурсией, поочерёдно задавая её фигуру для вставки, отличную от предыдущей.
Но главная проблема в том, что я не знаю как проверить оставшиеся клетки =\

Ci5 28.11.2007 12:00
Цитата:
Вместо того чтобы учить студентов первых-вторых курсов информатике, нам сунули в зубы *censored* учебник какого-то препода, в котором задачки не столько на знание Си, сколько на соответствие уровню умственного развития как минимум Шерлока Холмса или блин Цезаря и кто там самый умный был =\
ИМХО хороший программист - программист с хорошим нестандартным мышлением.

Дикс 28.11.2007 12:16
2 Ci5
согласен :( тока вот задачу надо решить к зимней сессии

spider-intruder 28.11.2007 13:00
11. Разместить на шахматной доске максимальное количество слонов и ладей так,
чтобы они не находились друг у друга " под боем" .

У тебя на картинке все ладьи под боем - или "под боем" не должны быть слоны с ладьями а друг с другом можно?

Итог задачи это втиснуть как можно больше "каких нибудь фигур" ну т.е. например 18 слонов это более удачная позиция чем 10 слонов и 2 ладьи???

Или кол во слонов и ладей (ладьев :-)) должно быть одинаковым?

Дикс 28.11.2007 13:21
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ШЕСТЬ

ZaCo 28.11.2007 13:50
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 работы поменял :-)
Мне просто интересна задача :)

>> "сложность правда будет не просто оценить, потому что сразу сказать сколько вариантов лишних отметает одна фигура не ясно"

В том то и дело :)

Дикс 28.11.2007 15:31
Хде ж я узнаю более подробное условие? Он наверно уже помер.
Надо довольствоваться текстом из учебника.

Насколько я понимаю - там нет разделения на масти. И ладья ладью бить не может.
Как можно делить на масти если у каждой стороны по настоящим правилам не может быть больше двух слонов и двух ладей?


Я вот чо заметил - все слоны стоят на тёмных клетках, все ладьи - на белых.
То что на скриншоте выше - в идеале всё должно ещё раз повториться и мы должны получить такой результат:

http://img136.imageshack.us/img136/1417/var1wu5.jpg

хмммм
я думаю надо попробовать тупо запускать функцию ещё раз, тогда она проставит два вторых столбца фигур, которых не хватает на первом скрине в первом посте.
но тогда какая тут нахрен рекурсия, если функция будет брать с нуля? =\
мм
надо запоминать максимальный Х и юзать его при вторичном и последующих (теоретически. так то они уже не понадобятся) проходах по доске.

spider-intruder 28.11.2007 16:27
y
 
Не верно - у тя получается 8 тех и 8 тех

Я вот придумал как разместить 8 слонов и 9 тур
Думаю дальше )

спустя минуту:
Знаю как 10 слонов и 8 тур...

Надо сначала придумать максимально число тех и тех фигур а потом методом от обратного сочинить алгоритм.

Ты ж ХЭКИРЧеГ - у тя должно быть все по хитрому ;-)


http://img522.imageshack.us/img522/1230/var1oe1dj0.jpg

вот смотри

Дикс 29.11.2007 08:30
Omg %)

и никакой я не хэкерчег, йа веб-дизайнер! меня воротит от нулей и единиц, я не хочу быть системным программером и экономить каждый байт!

я письмо преподу написал, буду ждать ответа с подробностями.

ZaCo 29.11.2007 12:36
2spider-intruder фигуры не должны бить друг друга, по-моему это в
условии написано. слон не может бить не только слона, но и ладью. хотя
конечно автор мог иметь вовсе что-то другое, тем не менее тогда можно
вообще ставить так:

*SSSSSSS
******L*
*****L**
****L***
***L****
**L*****
*L******
LSSSSSSS

но тогда смысл задачи ТЕРЯЕТСЯ - больше поставить никак нельзя, хотя бы
потому, что 14 - самое максимальное кол-во слонов которых можно
поставить тк 14 максимальное кол-во не пересекающихся диагоналей на
доске (диагонали не имеют права пересекаться тк их порождают сами
слоны), 8 - макисмальное кол-во ладей (очевидно), но тк любой вариант на
максимальную растоновку слонов будет съедать одну клетку диагонали, то
кол-во ладей 7. конечно, мы в общем случае никогда не имеет парва делать
общий максимум из максимума по слонам, однако в данной задаче если мы
возьмем не максимум, а например 13, то ладей можно будет поставить,
очевидно, лишь на одну больше (тк до этого было 7) => сумма общая не
меняется. при этом в задаче нас интересует общая сумма, тк не было
введено понятия цены одной фигуры по сравнению с другой - опять смысл
ТЕРЯЕТСЯ.

Дикс 29.11.2007 14:23
Ну вот, задача немного прояснилась:

> - все слоны одной масти?
Масть одна
> - в каком порядке надо ставить их на клетки? слон - ладья - слон?
Порядок не важен
> - вариант 10 ладей и 8 слонов (к примеру) приоритетнее чем 18 слонов?
В сумме должно быть максимальное количество, но хотя бы одна ладья и слон.
> Их должно быть по возможности одинаковое количество?
Нет.

ZaCo 30.11.2007 15:43
>>В сумме должно быть максимальное количество, но хотя бы одна ладья и слон.
тогда 13, http://zaco.info/shah.cpp

KEZ 01.12.2007 07:11
*SSSSSSS
******L*
*****L**
****L***
***L****
**L*****
*L******
LSSSSSSS

а отмеченая красным ладья разве не делает шах слонам, которые стоят сразу после нее (влево) ?

Joker-jar 01.12.2007 10:03
Задача немного туповатая. Когда я решал подобные задачи, ответ был не тривиален и зависел, чаще всего, от размера шахматной доски NxN (где N - входной параметр в опр. интервале). Здесь же, как я понимаю, подразумевается размер реальной доски 8x8 => ответ у задачи всегда один и тот же. Решай на листочке, потом подсунь преподу что то вроде

print res; // =)

<JOK3R> 01.12.2007 13:14
Хм, довольно интересно, надо подумать! =/

ZaCo 01.12.2007 13:32
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 и выход из рекурсии (это в самом начале функции).

ZaCo 02.12.2007 02:14
после сообщения о тупости задачи не ожидал более тупого ответа, принимая во внимание то, что решение я привел.

Joker-jar 02.12.2007 09:16
ZaCo, я говорил о тупости условия задачи. А то, что решение ты привел, эт не значит что оно единственное

KEZ 02.12.2007 10:39
ZaCo, перебор возможных комбинаций слонов и ладей можно реализовать в виде плагина к BruteNet ;)

ZaCo 02.12.2007 12:08
2Joker-jar в смысле не единственное? ты привел, если и решение, то не той задачи. более того, твой алгоритм не решает даже проблемы связанной с твоим условием, не относящегося к этому топику.

podkashey 06.01.2008 17:14
Какой тред нашел случайно... Прям в шоке..
ИМХО
X*******
**yyyyyy
*y*yyyyy
*yy*yyyy
*yyy*yyy
*yyyy*yy
*yyyyy*y
*yyyyyy*
Никто никого не бьет из друг друга, хотя бы по одному есть, кто есть кто насрать. Если нельзя чтобы вообще никто никого бил, то 8 на непересекающихся линиях. Хз че такая полемика... гы. Как запрограммировать незнаю - в фотошопе или пеинте ИМХО.
П.С. Ответ-то есть какой-нибудь уже?

KEZ 06.01.2008 17:48
podkashey, ты всмысле пытался нарисовать *** буквами "ХУЙ", или это реально решение...? )))))

ZaCo 06.01.2008 21:12
в двух постах этой темы же написал, что тогда смысл у задачи теряется, точнее программистский. чем вам моя реализация-то (выводит даже !позиции! слонов и ладей) не нравится?:) хотя тут интересен исключительно момент оптимизации алгоритма..

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,(CFileExc eption *)&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-ти значные результаты вывалятся в файл


Время: 20:53