Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Python → Перебір
Для відправлення відповіді ви повинні увійти або зареєструватися
І знову вітаю.
В мене проблемка, треба реалізувати функцію на перебір.
Я навіть уявити алгоритму не можу... Поясніть як можна зробити такий перебір.
Допоможіть!
Обираємо найдешевше (наприклад це тюльпани), і цілочислено ділимо сумм на ціну найдешеших квітів, отримуємо теоретичний максимум ітерації данного виду, а тепер в трьох вкладених цикла перебираємо ціну тієї або іншої квітки помножити на номер ітерації і зразу рахуємо, якщо вкладаємось - збільшуєм каунтер на одиницю, як ні - не збільшуємо. Результатом буде - каунтер. (Кантер спочатку знулити, в самому початку функції). Алгоритм дуже не оптимальний, проте перше, що в голову прийшло.
Ех, а могли б прикинутись шлангом і запостити задачу в "Цікаві задачі", отримали б і алгоритм, і рішення. 
Уточнення по умові: можна тратити не всі гроші? А то в мене boquet(1, 1, 1, 10) повертає 0, якщо треба потратити максимально можливу суму, то це навіть правильно.
Ех, а могли б прикинутись шлангом і запостити задачу в "Цікаві задачі", отримали б і алгоритм, і рішення.
Уточнення по умові: можна тратити не всі гроші? А то в мене boquet(1, 1, 1, 10) повертає 0, якщо треба потратити максимально можливу суму, то це навіть правильно.
гроші можуть лишитися
І ще одне: перестановки рахуються як один варіант?
Оцього я не врахував.
І ще одне: перестановки рахуються як один варіант?
Враховуються букети які містять різняться між собою різною кількістю квітів
тобто, нам всеодно в якому порядку увіти будуть в букеті, значення має лише кількість кожної із квіток у букеті
Chemist-i, ви ще неврахували те що парними к-сть квітів дарув не можна... Та я це добавив..
Отже, що вийшло
def bouquets(narcissus_price, tulip_price, rose_price, summ):
chepest = summ / min(narcissus_price, tulip_price, rose_price)
print chepest
counter = 0
for i in range(1, chepest+1):
for j in range(1, chepest+1):
for k in range(1, chepest+1):
if (i*narcissus_price + j * tulip_price + k*rose_price)>=summ and (i+j+k)% 2 != 0:
counter += 1
return counter
print bouquets(1,1,1,5) #має бути 34, рахує 62
print bouquets(2,3,4,10) # має бути 12, рахує 62
print bouquets(2,3,4,100) # має бути 4019, рахує 59524Десь помилка..
Варіант для любителів ФП (ще не тестив)
[code=python]from itertools import *
def bouquets(narcissus_price, tulip_price, rose_price, summ):
prices=[narcissus_price, tulip_price, rose_price]
min_price=min(prices)
return len(tuple(
filter (lambda price: price<=summ,
map (sum,
chain(
*map (lambda n:combinations_with_replacement(prices, n),
takewhile (lambda n: n*min_price<=summ,
count(1, step=2))))))))[/code]
Варіант для любителів ФП (ще не тестив)
[code=python]from itertools import *def bouquets(narcissus_price, tulip_price, rose_price, summ):
prices=[narcissus_price, tulip_price, rose_price]
min_price=min(prices)
return len(tuple(
filter (lambda price: price<=summ,
map (sum,
chain(
*map (lambda n:combinations_with_replacement(prices, n)
takewhile (lambda n: n*min_price<=summ,
count(1, step=2))))))))[/code]
Помилка
takewhile (lambda n: n*min_price<=summ,
^
SyntaxError: invalid syntax
У попередньому рядку кому забув (уже виправив). Кажу ж, не тестив.
def bouquets(narcissus_price, tulip_price, rose_price, summ): chepest = summ / min(narcissus_price, tulip_price, rose_price) print chepest counter = 0 for i in range(1, chepest+1): for j in range(1, chepest+1): for k in range(1, chepest+1): if (i*narcissus_price + j * tulip_price + k*rose_price)>=summ and (i+j+k)% 2 != 0: counter += 1 return counter print bouquets(1,1,1,5) #має бути 34, рахує 62 print bouquets(2,3,4,10) # має бути 12, рахує 62 print bouquets(2,3,4,100) # має бути 4019, рахує 59524Десь помилка..
Загальна сума витрат на квіти має бути менша за наявний бюджет, а в вас - більша: (i*narcissus_price + j * tulip_price + k*rose_price)>=summ
Кількість подарованих квітів повинна бути парна, тобто остача від ділення на 2 має дорівнювати нулю, а в вас - не дорівнює.
Можна враховувати що букет без якогось типу квітки - теж букет, тому не range(1, chepest+1), а range(chepest+1)
Раджу роздруковувати в циклі комбінації що виходять, допомагає зневаджувати:
print '%3d)' % counter, '(narsicces={})*{} + (tulips={})*{} + (roses={})*{} = {} <= {}'.format(
narcissus_price, i, tulip_price, j, rose_price, k, total, summ
)Дякую!!!
Загальна сума витрат на квіти має бути менша за наявний бюджет, а в вас - більша: (i*narcissus_price + j * tulip_price + k*rose_price)>=summ
Точно, помилився..
Кількість подарованих квітів повинна бути парна, тобто остача від ділення на 2 має дорівнювати нулю, а в вас - не дорівнює.
А тут не погоджуюся...
Не забути, що букети з парною (загальною) кількістю квітів живим дівчатам не дарують. Тести із некоректними даними не проводяться.
Можна враховувати що букет без якогось типу квітки - теж букет, тому не range(1, chepest+1), а range(chepest+1)
Саме так.. пропустив..
Давайте по індукції. Якщо є тільки один вид квітів, то матимемо int(summ/price) варіантів (int - ціла частина), якщо вважати "букет" без квітів за варіант, і на один менше. якщо не вважати. Якщо є два види квітів, то якщо першого виду 0, то другого - до int(summ/price[2]), якщо першого 1, то другого до int((summ-price[1])/price[2]), якщо першого виду i, то другого до int((summ-i*price[1])/price[2]), максимум першого, очевидно, int(summ/price[1]), а всього - сума в циклі по i int((summ-i*price[1])/price[2]). Для третього і т.д. ніби вже очевидно - зовнішні цикли...
bunyk написав:Кількість подарованих квітів повинна бути парна, тобто остача від ділення на 2 має дорівнювати нулю, а в вас - не дорівнює.
А тут не погоджуюся...
Задача написав:Не забути, що букети з парною (загальною) кількістю квітів живим дівчатам не дарують. Тести із некоректними даними не проводяться.
І це вже в мене не перший випадок. Добре що цього разу не з живою дівчиною помилився.
не з живою дівчиною помилився.
Хто про що подумав, а я про німецький анатомічний театр Ґюнтера фон Хаґенза 
Давайте по індукції. Якщо є тільки один вид квітів, то матимемо int(summ/price) варіантів (int - ціла частина), якщо вважати "букет" без квітів за варіант, і на один менше. якщо не вважати. Якщо є два види квітів, то якщо першого виду 0, то другого - до int(summ/price[2]), якщо першого 1, то другого до int((summ-price[1])/price[2]), якщо першого виду i, то другого до int((summ-i*price[1])/price[2]), максимум першого, очевидно, int(summ/price[1]), а всього - сума в циклі по i int((summ-i*price[1])/price[2]). Для третього і т.д. ніби вже очевидно - зовнішні цикли...
Я таки не поняв... Шо означає один чи 2 чи 3 види квітів?
Написав такий код
Та занадто довго(>15 s.) працює з bouquets(200,300,400,100000)
Потім оптимізував до такого
З "bouquets(200,300,400,100000) " працює 10 сек. Та превіряльник дальше пише що не вкладаюся в 15 сек., як можна його оптимізувати??
На ideone не падає, хоча там на час обмеження важке: http://ideone.com/f4hjgZ
Внутрішній цикл не потрібен, бо там просте ділення. Сортування дозволяє крутити меншу кількість циклів.
А ще інтуїція підказує, що там буде формула без циклів, якщо кількість грошей кратна НСК цін на квіти, і можна зменшити sum на таке кратне. Але ліньки виводити.
занадто довго(>15 s.) працює з bouquets(200,300,400,100000)
Мій варіант із цими параметрами до 2 хв. працює 
Для відправлення відповіді ви повинні увійти або зареєструватися