Задача про наименьшее количество купюр и рекурсия

@Take_it · Регистрация: 09.01.2016

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

Вот такая классическая задачка есть:
В некоторой стране используются денежные купюры достоинством в 1, 2, 4, 8, 16, 32 и 64. Дано натуральное число п. Как наименьшим количеством таких денежных купюр можно выплатить сумму п (указать количество каждой из используемых для выплаты купюр)? Предполагается, что имеется достаточно большое количество купюр всех достоинств.
С вечера что то не думалось, а вот с утра написал рекурсию. Ребят мне кажется я тут намудрил, как это упростить, если возможно(только рекурсия).

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
namespace kupur
{
    class Program
    {
        static void Podschet_kupyur(int sum, int kup)
        {
            if (kup > 0)
            {
                if (sum >= kup)
                {
                    int kolvo = sum / kup;
                    int count = sum % kup;
                    sum = count;
                    if (sum <= kup)
                    {
                        Podschet_kupyur(sum, kup / 2);
                    }
                    Console.WriteLine("Купюр номиналом {0}\t{1} штук", kup, kolvo);
                }
                else
                {
                    Podschet_kupyur(sum, kup / 2);
                }
            }
        }
        
        static void Main(string[] args)
        {
            Console.WriteLine("Введи сумму ");
            int s = Convert.ToInt32(Console.ReadLine());
            int k = 64;
            Podschet_kupyur(s, k);
            Console.ReadKey();
        }
    }
}

@afront · 07.03.2016, 14:51

Конечно рекурсия не единственный способ решения проблемы, но вполне уместный.
Здесь есть интересное обсуждения различных способов решения такой задачи
http://stackoverflow.com/quest... llar-value

@baliar · 07.03.2016, 23:08

Не знаю,можно ли это назвать рекурсией, но можно проверять сумму по модулю банкноты последовательным делением на 2 до тех пор, пока остаток равен нулю. Запоминаем последнее правильное решение в аккумуляторе. Вычитаем от введенного п сумму и продолжаем с остатком те же действия. Наверное, всё это можно сделать через рекурсию.

@abcdfg · 08.03.2016, 01:04

Можно сделать циклом while, используя степени двойки если надо могу написать

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

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            double count = 0, sumAnswer = 0,  res = 0;
            int bound = 0, i = 6;
 
            Console.WriteLine("Введи сумму ");
            int sum = int.Parse(Console.ReadLine());
 
            if(sum == 1)
            {
                sumAnswer = 1;
                Console.WriteLine(sumAnswer);
                Console.ReadKey();
            }
            do
            {
                if(sum < Math.Pow(2, i))
                {
                    --i;
                    continue;
                }
 
                count = sum / Math.Pow(2, i);
                bound = (int)count;
                sumAnswer += bound;
                res = sum % Math.Pow(2, i);
                int residue = (int)res;
                if (residue == 1)
                {
                    sumAnswer += 1;
                }
                sum = residue;
                --i;
 
            } while (i != 0);
 
            Console.WriteLine(sumAnswer);
            Console.ReadKey();
 
        }
    }
}

короче можно вот так

Добавлено через 24 минуты
И еще я тебе советую никогда не пиши так kupyur, kolvo.

@baliar · 08.03.2016, 15:11

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using System;
 
/*
 * В некоторой стране используются денежные купюры достоинством в 1, 2, 4, 8, 16, 32 и 64.
 * Дано натуральное число п. Как наименьшим количеством таких денежных купюр можно выплатить
 * сумму п (указать количество каждой из используемых для выплаты купюр)? Предполагается, что
 * имеется достаточно большое количество купюр всех достоинств.
 */
namespace Recursion
{
    class WrongDataException : Exception
    {
        public override string ToString()
        {
            return "Введены неправильные данные";
        }
    }
    class Recursion
    {
        int _n = 1;
        public void Initialization()
        {
            Console.WriteLine("Введите сумму выплаты (целое положительное число)");
            try
            {
                int temp = int.Parse(Console.ReadLine());
                if (temp > 0)
                    _n = temp;
                else throw new WrongDataException();
                _difference = _n;
            }
            catch (WrongDataException exc)
            {
                Console.WriteLine(exc);
            }
        }
 
        private int _biggestValue=64;
        private int _difference;
        private double DivideBanknoteByTwo()
        {
            int numberOfPapers = _difference/_biggestValue;
            if (numberOfPapers >= 1)
                _difference -= numberOfPapers*_biggestValue;
            
            if(_difference%_biggestValue==0)
                return numberOfPapers;
            _biggestValue /= 2;
            return (DivideBanknoteByTwo() + numberOfPapers);
        }
 
        public void ShowNumberOfBanknotes()
        {
            Console.WriteLine("Наименьшее количество банкнот, " +
                              "которыми можно расплатиться" +
                              " за {0} составляет {1}.",
                              _n, DivideBanknoteByTwo());
            Console.ReadKey();
        }
    }
 
    class Program
    {
        static void Main()
        {
            Recursion _recursion=new Recursion();
            _recursion.Initialization();
            _recursion.ShowNumberOfBanknotes();
        }
    }
}
/*
 * можно проверять сумму по модулю банкноты последовательным делением на 2 до тех пор, пока 
 * остаток равен нулю. Запоминаем последнее правильное решение в аккумуляторе. Вычитаем от введенного
 * п сумму и продолжаем с остатком те же действия. Наверное, всё это можно сделать через рекурсию.
 */

Добавлено через 17 минут
_difference = _n; лучше поставить в finally, чтобы избежать ошибки при неправильно введенных данных.

Добавлено через 2 часа 34 минуты
Ранее была не совсем верная логика.

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
using System;
 
/*
 * В некоторой стране используются денежные купюры достоинством в 1, 2, 4, 8, 16, 32 и 64.
 * Дано натуральное число п. Как наименьшим количеством таких денежных купюр можно выплатить
 * сумму п (указать количество каждой из используемых для выплаты купюр)? Предполагается, что
 * имеется достаточно большое количество купюр всех достоинств.
 */
namespace Recursion
{
    class WrongDataException : Exception
    {
        public override string ToString()
        {
            return "Введены неправильные данные";
        }
    }
    class Recursion
    {
        int _n = 1;
        public void Initialization()
        {
            Console.WriteLine("Введите сумму выплаты (целое положительное число)");
            try
            {
                int temp = int.Parse(Console.ReadLine());
                if (temp > 0)
                    _n = temp;
                else throw new WrongDataException();
            }
            catch (WrongDataException exc)
            {
                Console.WriteLine(exc);
            }
            finally {_difference = _n;}
        }
 
        private int _biggestValue=64;
        private int _difference;
        private int DivideBanknoteByTwo()
        {
            int numberOfPapers = _difference/_biggestValue;
            
            if(_difference%_biggestValue==0)
                return numberOfPapers;
 
            _difference -= numberOfPapers * _biggestValue;
            _biggestValue /= 2;
 
            return (DivideBanknoteByTwo() + numberOfPapers);
        }
 
        public void ShowNumberOfBanknotes()
        {
            Console.WriteLine("Наименьшее количество банкнот, " +
                              "которыми можно расплатиться" +
                              " за {0} составляет {1}.",
                              _n, DivideBanknoteByTwo());
            Console.ReadKey();
        }
    }
 
    class Program
    {
        static void Main()
        {
            Recursion _recursion=new Recursion();
            _recursion.Initialization();
            _recursion.ShowNumberOfBanknotes();
        }
    }
}
/*
 * можно проверять сумму по модулю банкноты последовательным делением на 2 до тех пор, пока 
 * остаток равен нулю. Запоминаем последнее правильное решение в аккумуляторе. Вычитаем от введенного
 * п сумму и продолжаем с остатком те же действия. Наверное, всё это можно сделать через рекурсию.
 */

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@afront 1498 / 1213 / 821 Регистрация: 29.02.2016 Сообщений: 3,631
	07.03.2016, 14:51
	Конечно рекурсия не единственный способ решения проблемы, но вполне уместный. Здесь есть интересное обсуждения различных способов решения такой задачи http://stackoverflow.com/quest... llar-value 0

@baliar 112 / 83 / 32 Регистрация: 10.08.2014 Сообщений: 420
	07.03.2016, 23:08
	Не знаю,можно ли это назвать рекурсией, но можно проверять сумму по модулю банкноты последовательным делением на 2 до тех пор, пока остаток равен нулю. Запоминаем последнее правильное решение в аккумуляторе. Вычитаем от введенного п сумму и продолжаем с остатком те же действия. Наверное, всё это можно сделать через рекурсию. 0

Опции темы