Поиск со случайным перебором

@Артём121 · Регистрация: 15.11.2010

Author24 — интернет-сервис помощи студентам

Помогите разобраться в задаче.
Условие: найти в заданной последовательности чисел с помощью случайного перебора наибольшее по мощности подмножество, сумма чисел в котором равна числу Фибоначчи.
Я вот не могу понять, как осуществляется случайный перебор. Может кто скажет алгоритм этого случайного перебора с примером

@Yurek · 29.12.2012, 21:39

Сообщение от Артём121

Может кто скажет алгоритм этого случайного перебора с примером

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

Pascal

program Generator; // Генератор неповторяющихся чисел
 
const
  n = 255; // Количество чисел в последовательности
 
var
  index : byte; // Случайные номера чисел в последовательности
  mng : set of byte := [1..n]; // Множество, состоящее из номеров чисел
 
begin
  randomize; // Встряхиваем коробочку с костяшками перед их выбрасыванием на стол
  while mng <> [] do // Работаем до опустошения множества номеров
  begin
    index := random(n) + 1; // Выбрасываем случайные числа из диапазона 1..255
    if index in mng then  // Проверка сгенерированного числа на вхождение ..
      write(index:4);     // .. в множество в его текущем состоянии
    mng := mng - [index]; // Исключаем из множества уже сгенерированный номер
  end;
end. // Финита

Не очень хороший алгоритм, но суть передаёт. Главный недостаток в возрастающем количестве итераций с каждым следующим номером.
Можно что-то по-круче придумать...

Добавлено через 6 часов 46 минут
Ах, ну да, забыл привязать это всё к твоей задаче, но наверно догадаться не сложно, что данный код генерирует номера элементов множества для их выборки в слечайном порядке, то есть переменная index должна быть использована для обращения к соответствующему числу из множества, обозначенного в задании.

@Артём121 · 29.12.2012, 21:58 **[ТС]**

Спасибо. Вы мне помогли разобраться.

@Артём121 66 / 65 / 13 Регистрация: 15.11.2010 Сообщений: 396 Записей в блоге: 1
		1
	Поиск со случайным перебором 28.12.2012, 21:51. Показов 1813. Ответов 2 Метки нет (Все метки) Помогите разобраться в задаче. Условие: найти в заданной последовательности чисел с помощью случайного перебора наибольшее по мощности подмножество, сумма чисел в котором равна числу Фибоначчи. Я вот не могу понять, как осуществляется случайный перебор. Может кто скажет алгоритм этого случайного перебора с примером 0

@Артём121 66 / 65 / 13 Регистрация: 15.11.2010 Сообщений: 396 Записей в блоге: 1
	29.12.2012, 21:58 [ТС]	3
	Спасибо. Вы мне помогли разобраться. 0

Поиск со случайным перебором

Решение