Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 11.11.2011, 19:43   #1
nextdrift
Новичок
Джуниор
 
Регистрация: 11.11.2011
Сообщений: 2
По умолчанию Не покидает чувство, что я допустил ошибку в алгоритме/коде (Python)

Сама задача:
"На ежедневную прогулку выводится группа 15 детей. Они построены по трое в пять рядов. Как построить группу, чтобы в ечении 7 дней подряд ни один ребёнок не гулял с каждым из своих соседей по тройке более одного раза"

Мой код на питоне:
Код:
#!/usr/bin/python
# -*- coding: utf-8 -*-

days = 7 # Кол-во дней

# функция создания массива рзмером old, с вложенным массивом размера child
def double_array (old, child):
    a = range(old)
    for i in a:
        a[i] = range(child)
        for ii in a[i]:
            a[i][ii] = 0
    return a


# словарь объектов
items = { i : { j : "no" for j in range(15) } for i in range(15) }

# первые элементы
first_item = { i : "no" for i in range(15)}

# функция находжения свободного объекта, 
# который не стоял с данным рядом
def search_free_item(item):
    for i in xrange(15):
        if items[item][i] == 'no' and i != item and item_status[i] == 'no':
            # записываем в словарь данные о том, что объект уже стоит в связке
            items[item][i] = items[i][item] =  item_status[i] = 'yes'
            return i
            break

# функция поиска нераставленного объекта
def search_item_status(status):
    
    for i in item_status:
        if item_status[i] == status and first_item[i] == 'no':
            item_status[i] = first_item[i] = 'yes'
            return i
            break

# функция размещения
# по позициям
def placement():  
    place = double_array(5, 3)
    r = 0
    while r < 5:
        
        p = 0
        
        while p < 3:

            if p == 0:
                free_item = search_item_status('no')
                place[r][p] = free_item
                p = 1
            
            elif p == 1:
                free_item = search_free_item(free_item)
                place[r][p] = free_item
                p = 2
            
            else:
                free_item = search_free_item(free_item)
                place[r][p] = free_item
                r = r + 1
                break
    return place
for i in xrange(days):
    # создаём словарь с данными о статусе расстановки
    item_status = {i:'no' for i in range(15) }
    print placement()
1. Проходим по матрице по строкам
1.1. В первый столбец строки вставляем элемент, который ещё не был задействован. И который ещё не стоял первым
1.2. Второй столбец. Ищем объект, который не стоял рядом с предыдущим. Сохраняем в хеше связь с прошлым
1.3. Третий столбец. Ищем объект, который не стоял рядом с предыдущим. Сохраняем в хеше связь с прошлым


Меня не покидает чувство, что я делаю что-то в корне не правильно. И решение должно быть куда более элегантное.
Сейчас у меня программа ломается на на 4 дне... Да и на втором тоже...
Код:
[endy@ND-PC Институт]$ python 1.py 
[[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, 10, 11], [12, 13, 14]]
[[1, 3, 0], [2, 4, 6], [5, 7, 9], [8, 10, 12], [11, 13, None]]
[[4, 0, 2], [7, 1, 5], [10, 3, 6], [13, 8, 9], [14, 11, 12]]
Traceback (most recent call last):
  File "1.py", line 74, in <module>
    print placement()
  File "1.py", line 61, in placement
    free_item = search_free_item(free_item)
  File "1.py", line 26, in search_free_item
    if items[item][i] == 'no' and i != item and item_status[i] == 'no':
KeyError: None

Последний раз редактировалось nextdrift; 11.11.2011 в 19:49.
nextdrift вне форума Ответить с цитированием
Старый 12.11.2011, 07:42   #2
nextdrift
Новичок
Джуниор
 
Регистрация: 11.11.2011
Сообщений: 2
По умолчанию

Может мне кто-то помочь? Где я не учёл что-то, из-за чего программа ломается?
nextdrift вне форума Ответить с цитированием
Старый 08.03.2013, 23:10   #3
vedma89
Новичок
Джуниор
 
Регистрация: 05.03.2013
Сообщений: 1
По умолчанию Вот моё решение

Тоже попалась эта задача мать её. Наверное условие придумали в конслагире чтобы скучно не было. Предлагаю своё решение задачи может правильно может нет. Разбил детей на пары. В условии так и спрашивается "как построить чёртову группу" мой ответ по парам. И уже потом крутить двумерным массивом передвигая второй столбец в верх 7 раз подряд. Короче вот код на с++,
Код:
#include <iostream>
using namespace std;

void _print_mas(int *mas, int n, int m)
  {
    cout << "\n";
    for (int i = 0; i < n; i++)
	  {
	    for (int j = 0; j < m; j++)
		  {
			cout << mas[i * m + j] << "\t";
		  }
	    cout << "\n";
	  }
  }

int main()
  {
      int ISX[5][3] = { {1, 2, 3},
			{4, 5, 6},
			{7, 8, 9},
			{10,11,12},
			{13,14,15},
		      };

	_print_mas(*ISX,5,3);
	
	int VTOR[8][2] = { {1, 8},
			   {2, 9},
			   {3,10},
			   {4,11},
			   {5,12},
			   {6,13},
			   {7,14},
			   {0,15}
			 };
	
	cout <<"\nДень 1";		 
	_print_mas(*VTOR,8,2);
	
	for (int d=2; d<8; d++)
	    {
		cout <<"\nДень"<<d;
		int push = VTOR[0][1];
		for (int i = 0; i < 7; i++)
		  {
			VTOR[i][1] = VTOR[i+1][1];
		  }
		VTOR[7][1]=push;
		_print_mas(*VTOR,8,2);
	    }

    return 0;
  }
может кому помогу
vedma89 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
где я допустил ошибку? sudik Помощь студентам 0 06.11.2011 17:38
Поиск ошибки в Python-коде [парсинг запроса и генерация ответа WebSocket] russian-stalker Python 0 03.06.2011 12:34
Что такое драматизм и драматическое чувство? Kasper1 Свободное общение 0 29.04.2011 16:52
Работа со строками. Написал программній код, но где-то допустил ошибку. NikitaNikita Помощь студентам 2 07.02.2011 16:32
Ошибка в алгоритме?Выдает ошибку после компиляции. Aerial Общие вопросы C/C++ 2 12.05.2010 16:52