ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
13 сообщений из 13, страница 1 из 1
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #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:13
| Ответить | Цитировать | Написать  
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #33166246
DocAl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DocAl
Участник
Множество всегда построенно из степеней двойки или же оно произвольное, удовлетворяющее указанному правилу?
...
Рейтинг: 0 / 0
14.07.2005, 15:17
| Ответить | Цитировать | Написать  
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #33166271
Фотография Berkut
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Berkut
Участник
DocAlМножество всегда построенно из степеней двойки или же оно произвольное, удовлетворяющее указанному правилу?Да, в данном случае множество построенно из степеней двойки.
...
Рейтинг: 0 / 0
14.07.2005, 15:24
| Ответить | Цитировать | Написать  
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #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:26
| Ответить | Цитировать | Написать  
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #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:33
| Ответить | Цитировать | Написать  
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #33166306
DocAl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DocAl
Участник
Ну так собственно в чём алгоритм-то, перевести число в двоичную систему?
...
Рейтинг: 0 / 0
14.07.2005, 15:35
| Ответить | Цитировать | Написать  
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #33166323
Фотография Berkut
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Berkut
Участник
DocAlНу так собственно в чём алгоритм-то, перевести число в двоичную систему?
Нет, надо определить те элементы множества, сумма которых дает X.
...
Рейтинг: 0 / 0
14.07.2005, 15:41
| Ответить | Цитировать | Написать  
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #33166329
DocAl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DocAl
Участник
Кхм... А что есть такое двоичное представление числа?? Ровно и есть представление в виде суммы степеней двойки.
...
Рейтинг: 0 / 0
14.07.2005, 15:43
| Ответить | Цитировать | Написать  
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #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:45
| Ответить | Цитировать | Написать  
Задача на нахождение разбиения (представления) числа в виде суммы других чисел множества
    #33166379
Фотография Berkut
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Berkut
Участник
Спасибо всем!

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


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