Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Python → Перебір
Для відправлення відповіді ви повинні увійти або зареєструватися
Q-bart написав:занадто довго(>15 s.) працює з bouquets(200,300,400,100000)
Мій варіант із цими параметрами до 2 хв. працює
Я вам щиро дякую, за допомогу,.. Проте я хочу не тільки здати завдання, а й зрозуміти..:) А якщо мені зараз ще вчити ФП...
На ideone не падає, хоча там на час обмеження важке: http://ideone.com/f4hjgZ
Найбільші вхідні дані
bouquets(10,199,99,20000)
bouquets(22,44,150,20000)І цей код на Ideone рахує неправильно..
І цей код на Ideone рахує неправильно..
Це зауваження неправильне.
Як якщо, для вхідних даних bouquets(200,300,400,100000) він повертає 7049112, а має 3524556
Давайте на простіших прикладах, щоб руками можна було перебрати. bouquets(1,1,1,2) скільки має давати?
3
[1 0 0 ]
[0 1 0 ]
[0 0 1 ]
А у мене 10 виходить:
[0 0 0]
[1 0 0]
[0 1 0]
[0 0 1]
[2 0 0]
[0 2 0]
[0 0 2]
[1 1 0]
[1 0 1]
[0 1 1]
Ну, лишається питання, чи вважати [0 0 0] букетом, але це за необхідності легко виправити - мінус один до результата. А у вас на 2 гривні виходить тільки 1 квітку за 1 гривню купити.
Але парну кількість квітів неможна використов.
я йолоп 
Проґавив умову
Добре, виправляюся: http://ideone.com/nywQU3
Тепер 3524556, і час виконання стерпний.
букети з парною (загальною) кількістю квітів живим дівчатам не дарують.
Чому ?
Я щось подібне чув від людей, які мають 60 років і більше.
Як на мене, то це забобон.
Просто традиція. Похоронні букети містять парну кількість квітів, святкові — непарну. У деяких країнах — навпаки.
Правильний код програми, тест пройшов
def bouquets(narcissus_price, tulip_price, rose_price, summ):
n=int(summ//narcissus_price)
k=int(summ//tulip_price)
p=int(summ//rose_price)
count=0
for i1 in range(0,n+1):
for i2 in range(0,k+1):
for i3 in range(0, p+1):
if i1*narcissus_price+i2*tulip_price+i3*rose_price<=summ:
if (i1+i2+i3)%2<>0:
count+=1
else:
break
return countОператор <> застарів.
Час виконання незадовільний (на ideone не проходить: http://ideone.com/bFlNkp)
Оператор <> застарів.
Час виконання незадовільний (на ideone не проходить: http://ideone.com/bFlNkp)
Які є поради по прискоренню/оптимізації програми?
koala написав:Оператор <> застарів.
Час виконання незадовільний (на ideone не проходить: http://ideone.com/bFlNkp)Які є поради по прискоренню/оптимізації програми?
Поміняти місцями дві умови:
Оскільки ті обчислення "важчі", ніж перевірка на парність, то на ідеоне тепер проходить.
Ви рахуєте багато зайвого:
import timeit
import math
def bouquets_3(narcissus_price, tulip_price, rose_price, summ): # koala
prices = sorted([narcissus_price, tulip_price, rose_price], reverse=True)
counter = 0
for i in range(math.floor(summ / prices[0]) + 1):
for j in range(math.floor((summ - i * prices[0]) / prices[1]) + 1):
last_count = math.floor((summ - i * prices[0] - j * prices[1]) / prices[2]) + 1
if (i + j) % 2 == 0:
counter += math.floor(last_count / 2)
else:
counter += math.ceil(last_count / 2)
return counter
def bouquets_2(narcissus_price, tulip_price, rose_price, summ): # ADR
prices = sorted([narcissus_price, tulip_price, rose_price], reverse=True)
count = 0
for count_0 in range(int(summ / prices[0] + 1)):
prices_of_0 = count_0 * prices[0]
for count_1 in range(int((summ - prices_of_0) / prices[1] + 1)):
count_2 = int((summ - prices_of_0 - count_1 * prices[1]) / prices[2]) # скільки можна купити
count += count_2 // 2 # тільки непарні (кожен другий)
if (count_0 + count_1) % 2 or count_2 % 2: # 0 0 1 та 1 0 0 також підходить
count += 1
return count
def bouquets(narcissus_price, tulip_price, rose_price, summ):
n = int(summ // narcissus_price)
k = int(summ // tulip_price)
p = int(summ // rose_price)
count = 0
for i1 in range(0, n + 1):
for i2 in range(0, k + 1):
for i3 in range(0, p + 1):
if i1 * narcissus_price + i2 * tulip_price + i3 * rose_price <= summ:
if (i1 + i2 + i3) % 2 != 0:
count += 1
else:
break
return count
assert bouquets(10, 199, 99, 20000), bouquets_2(10, 199, 99, 20000)
assert bouquets_3(10, 199, 99, 20000), bouquets_2(10, 199, 99, 20000)
assert bouquets(22, 44, 150, 20000), bouquets_2(22, 44, 150, 20000)
assert bouquets_3(22, 44, 150, 20000), bouquets_2(22, 44, 150, 20000)
print('assert done.')
for test_data in ('22, 44, 150, 20000',
'1, 10, 100, 1000',
'100, 100, 100, 1000'):
print('\nArguments: ' + test_data)
for author, func_name, cycles in (('koala', 'bouquets_3', 100),
('ADR', 'bouquets_2', 100),
('prosergii', 'bouquets', 2)):
print('{:10}: {:9.6f}'.format(author, timeit.timeit('{}({})'.format(func_name, test_data),
'from __main__ import {}'.format(func_name),
number=cycles) / cycles))Результат:
Arguments: 22, 44, 150, 20000
koala : 0.050158
ADR : 0.037348
prosergii : 7.963269
Arguments: 1, 10, 100, 1000
koala : 0.000913
ADR : 0.000671
prosergii : 0.272566
Arguments: 100, 100, 100, 1000
koala : 0.000128
ADR : 0.000095
prosergii : 0.0003471. Для чого рахувати "що буде, якщо 1000 перших квіток і 1000 других", якщо грошей є лише на 1000 і 500?
2. Для чого рахувати "що буде, якщо 1000 перших квіток, 1000 других і 0,1,2,3,4,5,6,... третіх", якщо можна порахувати скільки тих третіх можна купити?
Та й здається що цю задачу можна вирахувати аналітично. Хоча не впевнений.
Чи задача була саме перебрати всі варіанти?
Update:
Стоп. схожа версія вже була. Чому її не використовували?
Update:
Додав тести всіх версій.
Дякую за вашу активність!
Я писав цю програму сьогодні в рамках онлайн курсу "основи програмування". Сюди попав випадково, щось шукав для програми. Так як умова повністю збігалася, вирішив поділитися тим, що маю.
Так як умова повністю збігалася
Умова в першому повідомленні також з того самого курсу
на ideone проходить: http://ideone.com/WpsIGV
і на моєму за 3 секунди:
2016-06-16 10:39:24.982000
3524556
2016-06-16 10:39:27.294000Для відправлення відповіді ви повинні увійти або зареєструватися