VPF::[C] Задача о ферзях на доске m * n - Форум программистов

Янотик

Дата 16.12.2006, 20:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 16.12.2006
Где: Питер

Репутация: нет
Всего: нет

Помогите, пожалуйста! smile

Надо написать программу на C, решающую задачу о ферзях. Пользователь вводит размеры доски m*n(max 50*50). И количство ферзей(изначально оно стоит по умолчанию). Надо выполнять методом рекурсии.

Exception

Дата 16.12.2006, 20:56 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 4525
Регистрация: 26.12.2004

Репутация: нет
Всего: 186

А в чём суть задачи-то smile

Янотик

Дата 16.12.2006, 21:42 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 16.12.2006
Где: Питер

Репутация: нет
Всего: нет

Ну, надо расставить n ферзей (если n-это меньшая сторона доски) так чтобы ни один из них не угрожал другому.

Kuvaldis

Дата 17.12.2006, 03:19 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61

Янотик,
пользуемся поиском (хотя бы по нашему форуму)
смотри здесь

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Янотик

Дата 17.12.2006, 16:18 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 16.12.2006
Где: Питер

Репутация: нет
Всего: нет

Я там смотрела уже. Задачи похожие, но всетака не то.

Dov

Дата 17.12.2006, 20:57 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Цитата(Янотик @ 16.12.2006, 19:47

)

размеры доски m*n(max 50*50).

Цитата(Янотик @ 16.12.2006, 19:47

)

Надо выполнять методом рекурсии.

Янотик, не хочется тебя разочаровывать, но если ты возьмёшь доску даже в два раза меньшую, т.е. 25 х 25( и ферзей соответственно 25), то результатов работы программы ты, в обозримом будующем, наврядли дождёшься. Сама подумай. Если для доски 8 х 8 ( и ферзей соответственно 8) ты получишь более 90 вариантов, то для доски 12 х 12( и ферзей соответственно 12) - более 14000 варианов. Дальше считай сама.., я не доживу. smile

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

Гарри

Дата 18.12.2006, 20:08 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 28
Регистрация: 11.10.2006
Где: Германия

Репутация: нет
Всего: 1

Dov, а в чём проблема, 50x50 это же максимум, а тестируешь стандартно, 8x8

Pete

Дата 18.12.2006, 20:14 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 318
Регистрация: 5.1.2006
Где: Москва

Репутация: 7
Всего: 12

http://algolist.manual.ru/maths/combinat/queens.php

Добавлено @ 20:27
Примерно это когда-то переписывал (кажись, именно с алголиста) один мой знакомый (для 8-ми ферзей):

Код


#include <stdio.h>
#include <math.h>

int N = 8;
int array[8];
int count;
int table[8][8] = { {  1,  2,  3,  4,  5,  6,  7,  8 }, 
                    {  9, 10, 11, 12, 13, 14, 15, 16 }, 
                    { 17, 18, 19, 20, 21, 22, 23, 24 }, 
                    { 25, 26, 27, 28, 29, 30, 31, 32 }, 
                    { 33, 34, 35, 36, 37, 38, 39, 40 }, 
                    { 41, 42, 43, 44, 45, 46, 47, 48 }, 
                    { 49, 50, 51, 52, 53, 54, 55, 56 }, 
                    { 57, 58, 59, 60, 61, 62, 63, 64 } };
void answer( void ) 
{
  int i, ans = 0;
  
  for (i = 0; i < N; i++) {
    ans += table[i][ array[i + 1] - 1 ];
    printf( "%d ", table[i][ array[i + 1] - 1 ] );
  }
  printf( "Result: %d\t", ans );
}

int p( int k, int y ) 
{
  int i;
  for (i = 1; i < k && y != array[i] && abs(k - i) != abs( y - array[i] ); i++);
  
  return (i == k);
}

void bctr( int k ) 
{
  int i, y;
  
  for (y = 1; y <= N; y++) {
    if (p( k, y )) {
      array[k] = y;
      if (k == N) {
       for (i = 1; i <= N; i++) printf( "%d\t", array[i] );
       answer();
       printf( "\n" );
       count++;
      }
      bctr( k + 1 );
    }
  }
}

int main( void )
{
  bctr( 1 );
  printf("There are %d permutations if %d queens\n", count, N);
  
  return 0;
}

--------------------

Совет учиться на ошибках других бесполезен; научиться чему-либо можно только на собственных ошибках. (Бернард Шоу)
Не откладывай на завтра то, что можешь сделать сегодня. (Пословица)
А теперь выпишем точное значение числа пи... (Препод)
Жахни, Пендальф! © Гоблин

Dov

Дата 18.12.2006, 20:37 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Цитата(Гарри @ 18.12.2006, 19:08

)

Dov, а в чём проблема, 50x50 это же максимум, а тестируешь стандартно, 8x8

Гарри, у меня проблем нет, проблемы будут у того, кто захочет 50х50 протестировать. smile

Или даже 20х20, как я уже сказал. Не пойму только, зачем же такой максимум делать? smile

8х8 - самый лучший вариант для такой задачи, по крайней мере работать будет быстро. ИМХО. smile

--------------------

Гарри

Дата 18.12.2006, 20:56 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 28
Регистрация: 11.10.2006
Где: Германия

Репутация: нет
Всего: 1

Согласен

Янотик

Дата 18.12.2006, 21:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 16.12.2006
Где: Питер

Репутация: нет
Всего: нет

Цитата(Dov @ 17.12.2006, 20:57)

Ты это обьясни нашему преподу...
И это только I семестр. Что будет дальше! smile

Янотик

Дата 18.12.2006, 22:32 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 16.12.2006
Где: Питер

Репутация: нет
Всего: нет

Задача решилась, не без помощи моих замечательных одногруппников :hehe . Воовщем если кому интересно вот код. Правда тут верхний предел 100*100...

Код


#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream>
#include <cctype>

using namespace std;

FILE *outF;
char outS[100];

int dgn1[100][100],dgn2[100][100];
int goriz[100],vert[100];
int diag1[200],diag2[200];

int M;             
int N;

int Q; 
int Resh=0;

char desk[100][100];

void obnul()
{
int i,j,k=0;

for (i=0;i<100;i++)
    {
        goriz[i]=0; 
        vert[i]=0;
    }

for (i=0;i<200;i++)
    {
        diag1[i]=0; 
        diag2[i]=0;
    }

for (i=0;i<N;i++)
    {
        for (j=0;j<M;j++)
        {
            desk[i][j]='0';
        }
    }

for (i=0;i<M;i++)
    {
        k=i;
        for (j=0;j<N;j++)
            {
                dgn1[j][i]=k++;
            }

    }
for (i=0;i<M;i++)
    {
        k=i;
        for (j=N-1;j>=0;j--)
            {
                dgn2[j][i]=k++;
            }

    }

}


int svob(int x,int y)
{
 if (goriz[x]!=0) return 0;
 if (vert[y]!=0) return 0;
 if ((diag1[dgn1[y][x]])!=0) return 0;
 if ((diag2[dgn2[y][x]])!=0) return 0;
 return 1;
}

void putQueen(int x,int y)
{
  desk[y][x]='&';
  goriz[x]=1;
  vert[y]=1;
  diag1[dgn1[y][x]]=1;
  diag2[dgn2[y][x]]=1;
}

void delQueen(int x,int y){
  desk[y][x]='O';
  goriz[x]=0;
  vert[y]=0;
  diag1[dgn1[y][x]]=0;
  diag2[dgn2[y][x]]=0;
}


void zapis()
{
if (outF==NULL)
{
    cout<<"File opening error";
    cout<<"Press any key to exit";
    getch();
    return;
}
else
{
for (int i=0;i<N;i++)
    {
        for (int j=0;j<M;j++) 
        fprintf(outF,"%c ",desk[i][j]);
        fprintf(outF,"\n");
    }

 fprintf(outF,"\n\n");

}

}


int check(char *s)
{
for(int i=0;s[i]!='\0';i++)
    {
        if( !isdigit(s[i]) )
            return 1;

    }
return 0;
}



void trying(int c,int k)
{
int x,y;

do
    {
    x=c%M;
    y=c/M;
    
    if (svob(x,y))
        {
            putQueen(x,y);
            if (k==Q) 
                {
                    Resh++; 
                    printf("\rPlease Wait..."); 
                    zapis(); 
                    
                }
            
            else 
             trying(c,k+1);
            
            delQueen(x,y);
        }
    c++;
    }
while(c<(M*N));

}

void main()
{
//int i,j,tm,ts,tms,min,max;
char Mstring[100],Nstring[100],Qstring[100];

//    clrscr();
printf("                         Queens arrangment                         \n\n");
printf("\nInput width of chessboard(min=1,max=100) -> ");
scanf("%s",&Mstring);

    if (check(Mstring)==1)
    {
        cout<<"Incorrect input\n";
        cout<<"Press any key to exit\n";
        getch();
        return;
    }
    else
    {
        M=atoi(Mstring);
        if( (M<1) || (M>100) )
        {
            cout<<"Incorrect input\n";
            cout<<"Press any key to exit";
            getch();
            return;
        }
    }

printf("\nInput length of chessboard(min=1,max=100) -> ");
    scanf("%s",&Nstring);
    if (check(Nstring)==1)
    {
        cout<<"Incorrect input\n";
        cout<<"Press any key to exit\n";
        getch();
        return;
    }
    else
    {
        N=atoi(Nstring);
        if( (N<1) || (N>100) )
        {
            cout<<"Incorrect input\n";
            cout<<"Press any key to exit\n";
            getch();
            return;
        }
    }

printf("\nInput quantity of queens -> ");
    scanf("%s",&Qstring);
    if (check(Qstring)==1)
    {
        cout<<"Incorrect input\n";
        cout<<"Press any key to exit\n";
        getch();
        return;
    }
    else
        Q=atoi(Qstring);
    
        

    printf("\nInput name of output file -> ");
    scanf("%s",&outS);
    outF=fopen(outS,"wt");
        

    obnul();
   
    printf("\n\n");
    trying(0,1);

    printf("\nQuantity of the found variants=%d\n",Resh);
    
     fclose(outF);
    printf("\n\nSearching is complete. Press any key to exit\n");
    getch();
}

Это сообщение отредактировал(а) Янотик - 21.3.2007, 19:21

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »