Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества / 13 сообщений из 13, страница 1 из 1
14.07.2005, 15:13
    #33166239
Berkut
Berkut
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
Задача:

Код: plaintext
Есть множество из M уникальных элементов таких, что любое сочетание сумм элементов также будет уникальным.

Код: plaintext
Иными словами, такими элементами будут числа 1,2,4,8...

Код: plaintext
 Требуется  найти элементы этого множества, сумма которых равна известному числу X.

Например:
M (1, 2, 4, 8, 16)

X=15 Тогда разбиение числа будет следующим X = 1+2+4+8 = 15


X=10 разбиение X = 2 + 8 = 10


Есть у кого идеи по алгоритму решения?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:17
    #33166246
DocAl
DocAl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
Множество всегда построенно из степеней двойки или же оно произвольное, удовлетворяющее указанному правилу?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:24
    #33166271
Berkut
Berkut
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
DocAlМножество всегда построенно из степеней двойки или же оно произвольное, удовлетворяющее указанному правилу?Да, в данном случае множество построенно из степеней двойки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:26
    #33166277
DocAl
DocAl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
Перевести число в двоичную систему счисления?)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:26
    #33166279
Andres 1
Andres 1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
VB, VBA

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
Function ds(x As Long) As String
Dim m( 9 ) As Long
Dim lngTmp As Long
Dim strResult As String
Dim i As Long
  'Init stuff
  m( 0 ) =  1 
  m( 1 ) =  2 
  For i =  2  To UBound(m)
    m(i) =  2  ^ i
  Next i
  lngTmp = x
  strResult = x & " = "
  'Do the trick
  For i = UBound(m) To  0  Step - 1 
    If lngTmp >= m(i) Then
      strResult = strResult & m(i) & " + "
      lngTmp = lngTmp - m(i)
    End If
  Next i
  ds = Left(strResult, Len(strResult) -  3 )
End Function
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:33
    #33166298
Berkut
Berkut
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
Важное уточнение: (сори, что забыл сразу написать)

Элементы множества - целые положительные числа

Все возможные суммы элементов множества должны представлять непрерывную последовательность.

Т.е.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
M { 1 ,  2 ,  4 ,  8 }

 1 =  1      4 = 4   		 8 = 8 
 2 =  2      1 + 4 = 5 		 1 + 8 = 9 
 1 + 2 = 3     2 + 4 = 6 		 2 + 8 = 10 
         1 + 2 + 4 = 7 		 1 + 2 + 8 = 11 
			 4 + 8 = 12 
			 1 + 4 + 8 = 13 
			 2 + 4 + 8 = 14 
			 1 + 2 + 4 + 8 = 15

Поэтому генерирование самого множества можно представить в виде:
Код: plaintext
1.
2.
3.
a  = 2^(n-1)

, где n - количество элементов
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:35
    #33166306
DocAl
DocAl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
Ну так собственно в чём алгоритм-то, перевести число в двоичную систему?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:41
    #33166323
Berkut
Berkut
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
DocAlНу так собственно в чём алгоритм-то, перевести число в двоичную систему?
Нет, надо определить те элементы множества, сумма которых дает X.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:43
    #33166329
DocAl
DocAl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
Кхм... А что есть такое двоичное представление числа?? Ровно и есть представление в виде суммы степеней двойки.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:45
    #33166339
Andres 1
Andres 1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
Berkut DocAlНу так собственно в чём алгоритм-то, перевести число в двоичную систему?
Нет, надо определить те элементы множества, сумма которых дает X.
Так, собственно, это и есть перевод числа в двоичную систему:
10, например = 1010 = 8+2:
Код: plaintext
1.
2.
 1 0 1 0
 8 4 2 1
14 = 1110 = 8+4+2
Код: plaintext
1.
2.
 1 1 1 0
 8 4 2 1
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:45
    #33166340
Berkut
Berkut
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
DocAlКхм... А что есть такое двоичное представление числа?? Ровно и есть представление в виде суммы степеней двойки.
Согласен :)) Просто уже не догоняю...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2005, 15:53
    #33166379
Berkut
Berkut
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
Спасибо всем!

Как оказалось решение проще, чем я думал (в "ступор" попал).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
21.07.2005, 12:34
    #33177710
zloy den
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
Можно с извращениями(как обычно у меня:-) Зато подойдет для любого множества.
1.Создать массив из множства
2.Начать смотреть меньше ли элемент массива чем число? Если меньше, то запомнить элемент, а последующие разы суммировать с уже наденными элементами. алгоритм завершатся если сумма равна искомому числу или при дохождении до первого элемента(в этом случае выдается сообщение что такой суммы нет)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества / 13 сообщений из 13, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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