VPF::[C++] "11 Лунок" - Форум программистов

Web_Zlo

Дата 6.12.2007, 16:33 (ссылка)

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

Загрузка ...

Новичок

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

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

Доброго времени суток!
Решил и я в кое-то веки подкинуть Вам, уважаемые знатоки олимпиадную задачку....
Вот она: Игровая доска имеет 11 лунок, в которых лежат 5 черных и 5 белых шаров так, что 5 черных шаров лежит в пяти левых лунках, а 5 белых шаров лежит в пяти правых. Одна лунка между этими "пятерками" остается свободна. Требуется передвинуть черные шары на место белых, а белые – на место черных за наименьшее число ходов. Шар можно передвигать либо в соседнюю с ним пустую лунку, либо в пустую лунку, которая находится непосредственно за ближайшим шаром. Причем, белые шары разрешается двигать лишь влево, а черные – лишь вправо. Думаем, решаем, выдвигаем мысли! smile

Sartorius

Дата 6.12.2007, 16:43 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

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

Перебор с возвратом для этой задачи вполне подходит (Вариантов на каждом шаге немного (<=4), глубина рекурсии мала).

Это сообщение отредактировал(а) Sartorius - 6.12.2007, 16:44

Sartorius

Дата 7.12.2007, 01:33 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

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

Код


#include <stdio.h>

#define W 1
#define B 2
#define H 0
#define SIZE 11

char aPool[SIZE] = {W,W,W,W,W,H,B,B,B,B,B};

char holePos = 5; // initial position of the hole

bool isFilan()
{
    return aPool[0] == B && 
           aPool[1] == B &&
           aPool[2] == B &&
           aPool[3] == B &&
           aPool[4] == B &&           
           aPool[5] == H &&
           aPool[6] == W &&
           aPool[7] == W &&
           aPool[8] == W &&
           aPool[9] == W &&
           aPool[10] == W;
           
}

void processStep()
{
    static int iStep = 0;

    iStep ++;

    bool bChanged = false;
    // Nearesrt White ball 
    if (holePos > 0 && aPool[holePos - 1] == W)
    {
        bChanged = true;

        aPool[holePos] = W;
        holePos --;
        aPool[holePos] = H;

        processStep();// next Movement

        // lets undo

        aPool[holePos] = W;
        holePos ++;
        aPool[holePos] = H;
    }
    // Nexxt Whilt Ball
    if (holePos > 1 && aPool[holePos - 2] == W)
    {
        bChanged = true;

        aPool[holePos] = W;
        holePos -= 2;
        aPool[holePos] = H;

        processStep();// next Movement

        // lets undo

        aPool[holePos] = W;
        holePos += 2;
        aPool[holePos] = H;
    }
    // Nearest Black ball
    if ((holePos < SIZE - 1) && aPool[holePos + 1] == B)
    {
        bChanged = true;

        aPool[holePos] = B;
        holePos ++;
        aPool[holePos] = H;

        processStep();// next Movement

        // lets undo

        aPool[holePos] = B;
        holePos --;
        aPool[holePos] = H;
    }
    // Next Black ball
    if ((holePos < SIZE - 2) && aPool[holePos + 2] == B)
    {
        bChanged = true;

        aPool[holePos] = B;
        holePos += 2;
        aPool[holePos] = H;

        processStep();// next Movement

        // lets undo

        aPool[holePos] = B;
        holePos -= 2;
        aPool[holePos] = H;
    }

    if (!bChanged)// Final configuration
    {
        for (int i = 0; i < SIZE; i++)
        {
            printf("%d ", aPool[i]);
        }

        if (isFilan())
        {
            printf("FINAL %d steps", iStep);
        }

        printf("\n");
    }

    iStep --;

}

void main()
{
    processStep();
}

получается два симметричных по ходам решенияв 36 ходов.

Web_Zlo

Дата 7.12.2007, 16:01 (ссылка)

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

Загрузка ...

Новичок

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

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

Вполне приличный ответ. Я, хоть и perl программер smile

, но скажу, что ответ на 5. smile

А никто не хочет взяться за графическую реализацию сего творения?

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