(UTC)
  1С++ users forum › 1С++ и прочие расширения v7 › Курилка › Разминка для головы. Оптимальный алгоритм.
(Группа Модераторов: 1c++ moderator)
‹ Предыдущая Тема | Следующая Тема ›
Переключение на Главную Страницу Страницы: 1 2 [3]  ОтправитьПечать
Очень популярная тема (более 25 ответов) Разминка для головы. Оптимальный алгоритм. (число прочтений - 7987 )
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: Разминка для головы. Оптимальный алгоритм.
Ответ #30 - 22. Мая 2010 :: 17:58
Печать  
И еще одну проверочку забыл вставить:
Код
Выбрать все
Функция ПолучитьПарыДляИгр(спИгроковГруппы//:СписокЗначений
	,спВозможныхПар//:СписокЗначений
	)


	Для й=1 По спВозможныхПар.РазмерСписка() Цикл
		спНераспределенныхИгроков = СоздатьОбъект("СписокЗначений");
		спИгроковГруппы.Выгрузить(спНераспределенныхИгроков);
		Результат  = СоздатьОбъект("СписокЗначений");
		текПара = спВозможныхПар.ПолучитьЗначение(й);

		ПолучитьИгроковПары(текПара, Игрок1, Игрок2);
		Результат.ДобавитьЗначение(текПара);

		УдалитьИзСписка(спНераспределенныхИгроков, Игрок1, Игрок2);
		Если спНераспределенныхИгроков.РазмерСписка()=0 Тогда
			Возврат Результат;
		КонецЕсли;

		Для ж=1 По спВозможныхПар.РазмерСписка() Цикл
			текПара_2 = спВозможныхПар.ПолучитьЗначение(ж);
			Если текПара=текПара_2 Тогда Продолжить;		КонецЕсли;

			ПолучитьИгроковПары(текПара_2, Игрок1, Игрок2);
			Если (спНераспределенныхИгроков.НайтиЗначение(игрок1)=0) или (спНераспределенныхИгроков.НайтиЗначение(игрок2)=0)  Тогда
				Продолжить;
			КонецЕсли;

			Результат.ДобавитьЗначение(текПара_2);

			УдалитьИзСписка(спНераспределенныхИгроков, Игрок1, Игрок2);
			Если спНераспределенныхИгроков.РазмерСписка()=0 Тогда
				Возврат Результат;
			КонецЕсли;

		КонецЦикла;
	КонецЦикла;

	Возврат "Решений нет!";
КонецФункции	// ПолучитьПарыДляИгр
  
Наверх
 
IP записан
 
berezdetsky
1c++ power user
Отсутствует


barba non facit sisadminum

Сообщений: 1986
Местоположение: Москва
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: Разминка для головы. Оптимальный алгоритм.
Ответ #31 - 22. Мая 2010 :: 18:19
Печать  
При таком подходе для поиска больше, чем двух пар будут перебраны не все варианты. Вложенный цикл придётся вынести в рекурсивную функцию. Вариант без рекурсии мог бы выглядеть так:
Код
Выбрать все
	  Dim n = 6 ' 6-элементное множество
	  Dim k = 4 ' 4-элементные подмножества

	  Dim A(k - 1) As Integer

	  ' первое подмножество
	  For i = 1 To k
		A(i - 1) = i
	  Next

	  Dim p = k

	  Do While p >= 1
		For Each i In A
		    Console.Write("{0} ", i)
		Next
		Console.WriteLine()

		If A(k - 1) = n Then
		    p -= 1
		Else
		    p = k
		End If

		If p >= 1 Then
		    For i = k To p Step -1
			  A(i - 1) = A(p - 1) + i - p + 1
		    Next
		End If
	  Loop


Из сгенерированных таким образом комбинаций пар отобрать допустимые.
Из оставшихся выбрать ту, которая требует минимального количества перестановок от комбинации, полученной по рейтинговому принципу.
  
пароль как коньяк, чем больше звездочек, тем лучше
Наверх
Skype/VoIP  
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: Разминка для головы. Оптимальный алгоритм.
Ответ #32 - 22. Мая 2010 :: 18:37
Печать  
Цитата:
При таком подходе для поиска больше, чем двух пар будут перебраны не все варианты. Вложенный цикл придётся вынести в рекурсивную функцию.

Точно! Не зря я сомневался. Спасибо, что открыл глаза.

За алгоритм отдельное спасибо. Правда еще не въехал в него (видать спать пора).
а что такое "Dim n = 6 ' 6-элементное множество" ?  Нерешительный
  
Наверх
 
IP записан
 
berezdetsky
1c++ power user
Отсутствует


barba non facit sisadminum

Сообщений: 1986
Местоположение: Москва
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: Разминка для головы. Оптимальный алгоритм.
Ответ #33 - 22. Мая 2010 :: 18:44
Печать  
JohnyDeath писал(а) 22. Мая 2010 :: 18:37:
а что такое "Dim n = 6 ' 6-элементное множество" ?  Нерешительный

Это алгоритм генерации k-элементных подмножеств n-элементного множества. Числа 4 и 6 взяты для примера. Написан на VB.NET. Результат работы в консоли: Цитата:
1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 5
1 2 4 6
1 2 5 6
1 3 4 5
1 3 4 6
1 3 5 6
1 4 5 6
2 3 4 5
2 3 4 6
2 3 5 6
2 4 5 6
3 4 5 6
  
пароль как коньяк, чем больше звездочек, тем лучше
Наверх
Skype/VoIP  
IP записан
 
JohnyDeath
1c++ power user
1c++ donor
Отсутствует



Сообщений: 3050
Местоположение: Волгоград
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: Разминка для головы. Оптимальный алгоритм.
Ответ #34 - 22. Мая 2010 :: 18:48
Печать  
Понял. Спасибо.

Смутила строчка
Код
Выбрать все
If A(k - 1) = n Then
Т.е. конкретный элемент подмножества сравнивается с КОЛИЧЕСТВОМ элементов в множестве?
  
Наверх
 
IP записан
 
berezdetsky
1c++ power user
Отсутствует


barba non facit sisadminum

Сообщений: 1986
Местоположение: Москва
Зарегистрирован: 19. Мая 2006
Пол: Мужской
Re: Разминка для головы. Оптимальный алгоритм.
Ответ #35 - 22. Мая 2010 :: 18:51
Печать  
Не с количеством, а с последним элементом множества.
  
пароль как коньяк, чем больше звездочек, тем лучше
Наверх
Skype/VoIP  
IP записан
 
Переключение на Главную Страницу Страницы: 1 2 [3] 
ОтправитьПечать
‹ Предыдущая Тема | Следующая Тема ›
 
  « Главная ‹ Раздел Вверх  



Valid RSS Valid XHTML Valid CSS Powered by Perl Source Forge