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

@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 до тех пор, пока 
 * остаток равен нулю. Запоминаем последнее правильное решение в аккумуляторе. Вычитаем от введенного
 * п сумму и продолжаем с остатком те же действия. Наверное, всё это можно сделать через рекурсию.
 */

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@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