21

Re: Перебір

P.Y. написав:
Q-bart написав:

занадто довго(>15 s.) працює з bouquets(200,300,400,100000)

Мій варіант із цими параметрами до 2 хв. працює :(

Я вам щиро дякую, за допомогу,..  Проте я хочу не тільки здати завдання, а й зрозуміти..:)  А якщо мені зараз ще вчити ФП...

22

Re: Перебір

koala написав:

На ideone не падає, хоча там на час обмеження важке: http://ideone.com/f4hjgZ

Найбільші вхідні дані

bouquets(10,199,99,20000)
bouquets(22,44,150,20000)

І цей код на Ideone рахує неправильно..

23

Re: Перебір

Q-bart написав:

І цей код на Ideone рахує неправильно..

Це зауваження неправильне.

Подякували: Q-bart1

24

Re: Перебір

Як якщо, для вхідних даних bouquets(200,300,400,100000) він повертає 7049112, а має  3524556

25

Re: Перебір

Давайте на простіших прикладах, щоб руками можна було перебрати. bouquets(1,1,1,2) скільки має давати?

Подякували: Q-bart1

26 Востаннє редагувалося Q-bart (21.03.2015 22:12:49)

Re: Перебір

3
[1 0 0 ]
[0 1 0 ]
[0 0 1 ]

27

Re: Перебір

А у мене 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 гривню купити.

Подякували: Q-bart, leofun012

28

Re: Перебір

Але парну кількість квітів неможна використов.

29 Востаннє редагувалося koala (21.03.2015 22:35:46)

Re: Перебір

:[ я йолоп :( Проґавив умову
Добре, виправляюся: http://ideone.com/nywQU3
Тепер 3524556, і час виконання стерпний.

Подякували: Q-bart, ADR2

30 Востаннє редагувалося leofun01 (22.03.2015 03:56:39)

Re: Перебір

Q-bart написав:

букети з парною (загальною) кількістю квітів живим дівчатам не дарують.

Чому ?
Я щось подібне чув від людей, які мають 60 років і більше.
Як на мене, то це забобон.

31

Re: Перебір

Просто традиція. Похоронні букети містять парну кількість квітів, святкові — непарну. У деяких країнах — навпаки.

Подякували: leofun011

32

Re: Перебір

leofun01 написав:

Як на мене, то це забобон.

А як на мене, то це умова задачі. :D

Подякували: koala, bunyk, leofun013

33 Востаннє редагувалося prosergii (15.06.2016 15:32:30)

Re: Перебір

Правильний код програми, тест пройшов

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

34 Востаннє редагувалося koala (15.06.2016 16:59:32)

Re: Перебір

Оператор <> застарів.
Час виконання незадовільний (на ideone не проходить: http://ideone.com/bFlNkp)

35

Re: Перебір

koala написав:

Оператор <> застарів.
Час виконання незадовільний (на ideone не проходить: http://ideone.com/bFlNkp)

Які є поради по прискоренню/оптимізації програми?

36

Re: Перебір

prosergii написав:
koala написав:

Оператор <> застарів.
Час виконання незадовільний (на ideone не проходить: http://ideone.com/bFlNkp)

Які є поради по прискоренню/оптимізації програми?

Поміняти місцями дві умови:

http://ideone.com/JolAmG

Оскільки ті обчислення "важчі", ніж перевірка на парність, то на ідеоне тепер проходить.

37 Востаннє редагувалося ADR (16.06.2016 12:46:19)

Re: Перебір

Ви рахуєте багато зайвого:

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.000347

1. Для чого рахувати "що буде, якщо 1000 перших квіток і 1000 других", якщо грошей є лише на 1000 і 500?
2. Для чого рахувати "що буде, якщо 1000 перших квіток, 1000 других і 0,1,2,3,4,5,6,... третіх", якщо можна порахувати скільки тих третіх можна купити?

Та й здається що цю задачу можна вирахувати аналітично. Хоча не впевнений.

Чи задача була саме перебрати всі варіанти?

Update:
Стоп. схожа версія вже була. Чому її не використовували?

Update:
Додав тести всіх версій.

Подякували: Master_Sergius, koala, prosergii, Chemist-i, leofun015

38

Re: Перебір

Дякую за вашу активність!
Я писав цю програму сьогодні в рамках онлайн курсу "основи програмування". Сюди попав випадково, щось шукав для програми. Так як умова повністю збігалася, вирішив поділитися тим, що маю.

39

Re: Перебір

prosergii написав:

Так як умова повністю збігалася

Умова в першому повідомленні також з того самого курсу

40

Re: Перебір

на ideone проходить: http://ideone.com/WpsIGV
і на моєму за 3 секунди:

2016-06-16 10:39:24.982000
3524556
2016-06-16 10:39:27.294000