Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Help...нужен алгоритм / 12 сообщений из 12, страница 1 из 1
29.06.2003, 15:36
    #32194495
Lent
Lent
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Help...нужен алгоритм
Зравствуйте господа
Извините за ламерский вопрос..но у меня уже честно говоря
башка совсем опухла...собсно дело вот в чем,
есть некий набор цифр:
20, 40, 50 , 10 , 5, 10 ,25.11, 14.55 ...и т.д (но не до бесконечности)
и есть число , к примеру 30,
нужен четкий алгоритм поиска слагаемых (из вышеуказанного набора) в сумме дающих это число (30), причем вариантов может быть несколько...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2003, 17:01
    #32194518
sab0tage
sab0tage
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Help...нужен алгоритм
Потому что алгоритм для двух слогаемых решается слету а вот для неопределенного числа надо немного подумать!,

для двух, предположим твои цифры в массиве 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
| Ответить | Цитировать | Написать  
29.06.2003, 18:17
    #32194543
Lent
Lent
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Help...нужен алгоритм
О тож :)
Слагаемых может быть несколько...
Причем и несколько вариантов наборов этих слагаемых, типа :
10+10+10=30, 15+10+5=30, ... и т.д.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2003, 21:08
    #32194571
mahoune
mahoune
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Help...нужен алгоритм
Ну во-первых, надо отбрасывать все числа значение которых больше или равно знанию которое необходимо получить! Более того все это надо делать рекурсивно.

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

Код: 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
| Ответить | Цитировать | Написать  
29.06.2003, 21:34
    #32194576
mahoune
mahoune
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Help...нужен алгоритм
тут слегка оплошал я:
Код: 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
| Ответить | Цитировать | Написать  
29.06.2003, 21:36
    #32194577
mahoune
mahoune
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Help...нужен алгоритм
Еще надо добавить проверку, может и всеми элементами нельзя получить искомого значения!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2003, 23:01
    #32194592
c127
c127
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Help...нужен алгоритм
Если я не ошибаюсь, это задача о рюкзаке или сводится к ней. Она NP-сложная. Алгоритмы есть, поищи в интернете.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.06.2003, 03:11
    #32194616
Lent
Lent
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Help...нужен алгоритм
Мда,...Спасибо тем кто не поленился...без шуток! СПАСИБО!
А тем , кто повыеб... ну ...тоже спасибо...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.06.2003, 10:30
    #32194743
mahoune
mahoune
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Help...нужен алгоритм
А ведь интересно, должно быть другое решение, не перебором?!

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

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

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


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