Определить количество комбинаций шайб, гаек и болтов для общей суммы покупки в 100 рублей

@Pavel Rem · Регистрация: 15.07.2016

Author24 — интернет-сервис помощи студентам

Задачка по программированию.
Дано:
Стоимость Болтов =10, Гаек=5, Шайб =0.5;
Определить количество комбинаций для общей суммы покупки в 100 рублей. При этом количество единиц товара при любой комбинации должна быть равна 100;

Ответ: Количество комбинаций = 1;
Болтов -1, Гаек -9, Шайб - 90;

C++

#include < iostream>
#include <clocale>
using namespace std;
 
void main() {
    setlocale(LC_ALL, "Rus");
    int cnt = 0, kol = 100;
    float sum = 100, c1 = 10, c2 = 5, c3 = 0.5, x = 0, y = 0, z = 0;
    for (x = 0; x <= kol; x++) {
        for (y = 0; y <= kol; y++)
            for (z = 0; z <= kol; z++)
                if (x + y + z == kol && (x*c1) + (y*c2) + (z*c3) == sum) {
                    cnt++; cout << "Болтов-" << x << " " << "Гаек-" << y << " " << "Шайб-" << z << " " << endl;
                }
    }
    cout << "Количество комбинаций =" << cnt << endl;
    system("pause");
}

Данный код выполняет миллион итераций для нахождения одного правильного значения. Можно ли сократить количество циклов добавив некую логическую закономерность которую я не заметил? Или улучшить код?

@~~MansMI~~ · 16.08.2016, 14:39

C++

    for (x = 0; x <= kol; x++) {
        for (y = 0; y+x <= kol; y++)
        {
            z=kol-y-x;

@avgoor · 16.08.2016, 14:55

Сообщение от Pavel Rem

Можно ли сократить количество циклов добавив некую логическую закономерность которую я не заметил? Или улучшить код?

Конечно можно. У вас три неизвестных (x ,y, z) и два уравнения (Cx*x+Cy*y+Cz*z=100 и Cx+Cy+Cz=100).
Можно обойтись одним циклом. Фиксируем x на каждой итерации (т.к. его стоимость самая большая - потребуется меньше всего итераций, пока Cx*x не превысит 100). Все у нас известен x и Cx*x - переносим их в правую часть и решаем систему из двух уравнений с двумя неизвестными. Даже решать не нужно, достаточно проверить, что решения целые (Это будет видно из решения в общем виде).

Возможно ли получить ответ вообще без цикла - надо подумать, что лень

@warhast · 16.08.2016, 15:53

шаг 1. Очевидно, что количество шайб кратно 10 - иначе не получить ровно 100 рублей. Далее проверяем только кратные 10 значения.
шаг 2. Если шайб менее 90 (80 и т.п. - других позиций >= 20, что при минимальной цене в 5 выводит за бюджет), если более 90 - не весь бюджет будет освоен. То есть остается распределить 10 позиций и 55 рублей.
шаг 3. далее или перебираем или вычитаем из 55 10*(цена самой дешевой позиции), а разницу делим на (цена болта - цена гайки), результат - сколько болтов. Остальное гайки.
Так как задачка на программирование, то вспоминаем предпочтения препода по объемам кода и либо ограничиваемся перебором 11*21*11 вариантов (шайб - от 0 до 100 с шагом 10, гаек - 0..20 с шагом 1, болтов 0..10, еще можно при выходе за бюджет или сумму переменных циклов сворачивать вложенные циклы) либо оформляем в код размышения выше.

@_Ivana · 16.08.2016, 22:47

Сообщение от avgoor

Возможно ли получить ответ вообще без цикла - надо подумать, что лень

x + y + z= 100
10x + 5y + 0.5z = 100
Избавляемся от z (из удвоенного второго вычитаем первое):
19x + 9y = 100
Перебираем руками целые x от 0 до 5 - это несложно.

ЗЫ Ну или как у Поля Дирака: 10 болтов, -10 гаек и 100 шайб

@avgoor · 17.08.2016, 11:57

Сообщение от _Ivana

Перебираем руками целые x от 0 до 5 - это несложно.

Я то же самое писал

Я имел ввиду через какие-нибудь функции Эйлера и т.п.

@_Ivana · 17.08.2016, 14:14

avgoor, в принципе, если бы вариантов было не 6 а побольше, можно было бы подумать про более серьезные алгоритмы отсечения лишних вариантов, и что-нибудь вывести из этого, и т.п. Но поскольку 6 вариантов перебрать руками - пара секунд, то энергетически выгоднее не искать сложностей

@avgoor · 17.08.2016, 16:36

Не по теме:

Сообщение от _Ivana

ЗЫ Ну или как у Поля Дирака: 10 болтов, -10 гаек и 100 шайб

А это мысль! Если развить идею: откаты удобно считать через комплексные числа с мнимыми шайбами. :D

@_Ivana · 17.08.2016, 17:02

Не по теме:

avgoor, да, но если расширить множество допустимых решений до комплексных чисел, то чисто мнимые шайбы так придется компенсировать мнимыми частями болтов и гаек - результирующая сотня должна быть красивой и действительной :)

Добавлено через 9 минут

Не по теме:

ЗЫ avgoor, кстати, я тут на тему этой задачки свою создал - про банки и Васю, там в конце концов общими усилиями уточнили условие, можете полюбопытствовать.

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	16.08.2016, 14:55	3
	Сообщение от Pavel Rem Можно ли сократить количество циклов добавив некую логическую закономерность которую я не заметил? Или улучшить код? Конечно можно. У вас три неизвестных (x ,y, z) и два уравнения (Cxx+Cyy+Czz=100 и Cx+Cy+Cz=100). Можно обойтись одним циклом. Фиксируем x на каждой итерации (т.к. его стоимость самая большая - потребуется меньше всего итераций, пока Cxx не превысит 100). Все у нас известен x и Cx*x - переносим их в правую часть и решаем систему из двух уравнений с двумя неизвестными. Даже решать не нужно, достаточно проверить, что решения целые (Это будет видно из решения в общем виде). Возможно ли получить ответ вообще без цикла - надо подумать, что лень 1

@warhast 27 / 26 / 6 Регистрация: 02.02.2014 Сообщений: 96
	16.08.2016, 15:53	4
	шаг 1. Очевидно, что количество шайб кратно 10 - иначе не получить ровно 100 рублей. Далее проверяем только кратные 10 значения. шаг 2. Если шайб менее 90 (80 и т.п. - других позиций >= 20, что при минимальной цене в 5 выводит за бюджет), если более 90 - не весь бюджет будет освоен. То есть остается распределить 10 позиций и 55 рублей. шаг 3. далее или перебираем или вычитаем из 55 10(цена самой дешевой позиции), а разницу делим на (цена болта - цена гайки), результат - сколько болтов. Остальное гайки. Так как задачка на программирование, то вспоминаем предпочтения препода по объемам кода и либо ограничиваемся перебором 1121*11 вариантов (шайб - от 0 до 100 с шагом 10, гаек - 0..20 с шагом 1, болтов 0..10, еще можно при выходе за бюджет или сумму переменных циклов сворачивать вложенные циклы) либо оформляем в код размышения выше. 1

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	16.08.2016, 22:47	5
	Сообщение от avgoor Возможно ли получить ответ вообще без цикла - надо подумать, что лень x + y + z= 100 10x + 5y + 0.5z = 100 Избавляемся от z (из удвоенного второго вычитаем первое): 19x + 9y = 100 Перебираем руками целые x от 0 до 5 - это несложно. ЗЫ Ну или как у Поля Дирака: 10 болтов, -10 гаек и 100 шайб 0

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	17.08.2016, 11:57	6
	Сообщение от _Ivana Перебираем руками целые x от 0 до 5 - это несложно. Я то же самое писал Я имел ввиду через какие-нибудь функции Эйлера и т.п. 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	17.08.2016, 14:14	7
	avgoor, в принципе, если бы вариантов было не 6 а побольше, можно было бы подумать про более серьезные алгоритмы отсечения лишних вариантов, и что-нибудь вывести из этого, и т.п. Но поскольку 6 вариантов перебрать руками - пара секунд, то энергетически выгоднее не искать сложностей 0

@avgoor
	17.08.2016, 16:36 #8
	Не по теме: Сообщение от _Ivana ЗЫ Ну или как у Поля Дирака: 10 болтов, -10 гаек и 100 шайб А это мысль! Если развить идею: откаты удобно считать через комплексные числа с мнимыми шайбами. :D 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	17.08.2016, 17:02	9
	Не по теме: avgoor, да, но если расширить множество допустимых решений до комплексных чисел, то чисто мнимые шайбы так придется компенсировать мнимыми частями болтов и гаек - результирующая сотня должна быть красивой и действительной :) Добавлено через 9 минут Не по теме: ЗЫ avgoor, кстати, я тут на тему этой задачки свою создал - про банки и Васю, там в конце концов общими усилиями уточнили условие, можете полюбопытствовать. 0

Опции темы