Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.06.2009, 21:50
Новичок

Отправить личное сообщение для konstantin Посмотреть профиль Найти все сообщения от konstantin
 
Регистрация: 08.06.2009
Сообщений: 14

Строки неодинаковых чисел постоянной суммы
Задача. Написать код на Паскале, который генерирует строки
заданной суммы с заданным количеством неповторяющихся чисел.
Массив чисел для генерации представляет собой последовательность от
1 до N(Max).
Помогите, пожалуйста.
  #2  
Старый 08.06.2009, 21:58
гость2

 
Сообщений: n/a

Могу написать на Python, подойдет? А паскаля у меня нет.

Цитата:
Массив чисел для генерации представляет собой последовательность от 1 до N(Max).
И что вы этим хотите сказать?
То что числа в последовательности должны быть целыми числами от 1 до N, или что? N - это число чисел в последовательности (т.е. получатся перестановки), или просто еще один параметр?

Цитата:
строки заданной суммы
Как у строки может быть сумма? Сумма ASCII-кодом её символов, что ли? Или же имеется в виду сумма чисел в последовательности, представленной этой строкой?
  #3  
Старый 09.06.2009, 08:46
Новичок

Отправить личное сообщение для konstantin Посмотреть профиль Найти все сообщения от konstantin
 
Регистрация: 08.06.2009
Сообщений: 14

гость2,

Можно ли код Python транслировать в Pascal? Или надо установить?

Последовательность чисел [1..N] означает, что генерация не
бесконечная и N - максимальный элемент перестановки.

Сумма строки (а это числа) означает "сумма чисел в
последовательности, представленной этой строкой"
  #4  
Старый 09.06.2009, 09:03
гость

 
Сообщений: n/a

Цитата:
Последовательность чисел [1..N] означает, что генерация не
бесконечная и N - максимальный элемент перестановки.
Непонятно.

Так количество этих чисел фиксировано одним числем? Или нет - т.е. по сути генерируем все размещения из N всех возможных длин с заданной суммой S?
  #5  
Старый 09.06.2009, 10:17
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

konstantin,
Верно ли, что задачу можно сформулировать так -
выбрать K чисел из диапазона 1..N так, чтобы сумма была S
?
  #6  
Старый 09.06.2009, 10:33
Новичок

Отправить личное сообщение для konstantin Посмотреть профиль Найти все сообщения от konstantin
 
Регистрация: 08.06.2009
Сообщений: 14

Ответ для MBo: Совершенно верно. Но главное условие: в
полученной строке числа не должны повторяться. Строк типа
2 2 2 4 7 12 27
не должно быть. А вот такие могут быть:
2 4 7 15 16 28 37
  #7  
Старый 09.06.2009, 10:56
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

ОК.
Каковы диапазоны чисел K, Sum и N?

Исправил формализацию задачи:

- это задача получения разбиения Sum на K неповторяющихся слагаемых,не больших N

Последний раз редактировалось MBo, 09.06.2009 в 13:56.
  #8  
Старый 09.06.2009, 13:39
Новичок

Отправить личное сообщение для konstantin Посмотреть профиль Найти все сообщения от konstantin
 
Регистрация: 08.06.2009
Сообщений: 14

К = 10 и меньше,
N = 50 и меньше,
Sum = 300 и меньше
  #9  
Старый 09.06.2009, 13:58
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Я неверно задачу классифицировал, исправил пост выше. Для генерации всех строк вполне подойдет рекурсивный метод.
  #10  
Старый 09.06.2009, 14:05
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Код:
def diff_partitions(Sum, K, N, lst, Minn = 1):
    '''Enumerates integer partitions of Sum with different parts <= N'''
    if K == 0:
        if Sum == 0:
            print(lst)
        return
    for i in range(Minn, min(Sum + 1, N + 1)):
        diff_partitions(Sum - i, K - 1, N, lst + [i], i + 1)
  
diff_partitions(10, 3, 6, [])

Последний раз редактировалось MBo, 09.06.2009 в 16:19.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Агоритм выделение суммы полных квадратов Jim Математические алгоритмы 4 19.10.2009 00:09
последовательности длины N из чисел 1,2..M на заданную сумму элементов строки mayasar Оффтопик 9 20.03.2009 22:18
Задача оплаты суммы с помощью ограниченого количества банкнот pro Математические алгоритмы (другое) 8 23.12.2008 21:16
Корень из суммы квадратов Michael_K Математические алгоритмы (другое) 19 15.04.2008 01:07
Помагите написать алгоритм выплаты суммы денег... гость Задачи 1 22.10.2007 23:00