powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Help...нужен алгоритм
12 сообщений из 12, страница 1 из 1
Help...нужен алгоритм
    #32194495
Lent
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Зравствуйте господа
Извините за ламерский вопрос..но у меня уже честно говоря
башка совсем опухла...собсно дело вот в чем,
есть некий набор цифр:
20, 40, 50 , 10 , 5, 10 ,25.11, 14.55 ...и т.д (но не до бесконечности)
и есть число , к примеру 30,
нужен четкий алгоритм поиска слагаемых (из вышеуказанного набора) в сумме дающих это число (30), причем вариантов может быть несколько...
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194518
sab0tage
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Потому что алгоритм для двух слогаемых решается слету а вот для неопределенного числа надо немного подумать!,

для двух, предположим твои цифры в массиве t:array [1..n]: of real;
тогда
for i:=1 to n do
for j:=n-i to n do
begin
if t +t[j]=30 then {}

end;
вот так.
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194543
Lent
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
О тож :)
Слагаемых может быть несколько...
Причем и несколько вариантов наборов этих слагаемых, типа :
10+10+10=30, 15+10+5=30, ... и т.д.
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194571
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну во-первых, надо отбрасывать все числа значение которых больше или равно знанию которое необходимо получить! Более того все это надо делать рекурсивно.

Не проверял, но как-то так!

Код: plaintext
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.
Dim Массив
Dim Массив_Проверяемые
Dim Что_Ищим
Function FindWhat(Сколько_Осталось)
  FindWhat = False

  ' Проходим по всем элементам
  For t=0 to Длинна(Массив)

    ' Исключая те которые уже выбрали на предыдущих рекурсиях
    If Массив_Проверяемые[t]=False Then

      ' Если текущее меньше оставшегося
      If Массив[t]<Сколько_Осталось Then
        result = t

        ' Заносим текущие в проверяемые
        Массив_Проверяемые[t]=True

        ' Рекурсивно вызываем дальнейший поиск
        f_r = FindWhat(Сколько_Осталось-Массив[t])
      End If

      Если вдруг подобрали - выводим
      If Массив[t]=Сколько_Осталось Then
        Write "Получить " & Что_Ищим & " можно сложив:"
        For i=0 to Массив_Проверяемые
          If Массив_Проверяемые[i]=True Then
            Write Массив[i] & "; "
          End If
        Next i
        Write vbNewLine
        FindWhat = True
      End If
    End If
  Next t
  FindWhat=result
End Function

' Вызов
FindWhat(Что_Ищим)
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194576
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
тут слегка оплошал я:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
 -- Вместо:
 
      If Массив[t]=Сколько_Осталось Then

 -- Надо:
 
      If Сколько_Осталось= 0  Then

 -- Ну и некоторые другие пережитки прошлого почикать надо:
 


В общем вот:
Код: plaintext
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.
Dim Массив
Dim Массив_Проверяемые
Dim Что_Ищим
Function FindWhat(Сколько_Осталось)
   -- Если вдруг подобрали - выводим
 
  If Сколько_Осталось= 0  Then
    Write  "Получить "  & Что_Ищим &  " можно сложив:" 
    For i= 0  to Массив_Проверяемые
      If Массив_Проверяемые=True Then
        Write Массив[i] &  "; " 
      End If
    Next i
    Write vbNewLine
  Else If
     [i]-- Проходим по всем элементам
 
    For t= 0  to Длинна(Массив)
       -- Исключая те которые уже выбрали на предыдущих рекурсиях
 
      If Массив_Проверяемые[t]=False Then
         -- Если текущее меньше оставшегося
 
        If Массив[t]<Сколько_Осталось Then
           -- Заносим текущие в проверяемые
 
          Массив_Проверяемые[t]=True
           -- Рекурсивно вызываем дальнейший поиск
 
          FindWhat(Сколько_Осталось-Массив[t])
        End If
      End If
    Next t
  End If

End Function

 -- Вызов
 
FindWhat(Что_Ищим)
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194577
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Еще надо добавить проверку, может и всеми элементами нельзя получить искомого значения!
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194592
c127
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Если я не ошибаюсь, это задача о рюкзаке или сводится к ней. Она NP-сложная. Алгоритмы есть, поищи в интернете.
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194616
Lent
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Мда,...Спасибо тем кто не поленился...без шуток! СПАСИБО!
А тем , кто повыеб... ну ...тоже спасибо...
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194743
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А ведь интересно, должно быть другое решение, не перебором?!

mahoune
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194889
ZrenBy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
>>А ведь интересно, должно быть другое решение, не перебором?!

Ага, только не очень эффективное.

Метод Монте-Карло.
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32194929
Oleg_Martynov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
с127 прав. Это и впрямь задача об укладке ранца. Она же коммивояжёра, она же составления расписаний, она же ... Если чисел много (10000, например) - то можно не дождаться решения, а если дождаться - то не оптимального. Если нужны все возможные варианты - то, IMHO, только перебором, и очень долго - время решения растёт даже не экспотенциально. Прикиньте время выполнения такого перебора - м.б., есть возможность как-то переформулировать задачу - например, не искать все решения - тогда можно использовать методы отсечения?
...
Рейтинг: 0 / 0
Help...нужен алгоритм
    #32199926
anonymous@lor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
да, экспотенциально -- это круто!
...
Рейтинг: 0 / 0
12 сообщений из 12, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Help...нужен алгоритм
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]