Вычислить минимальное количество банкнот и монет в сумме

@ElenaPrg · Регистрация: 28.01.2014

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

Ребята, очень надеюсь на вашу помощь.
Чтобы получить зачёт, надо написать программу в паскале. Мне попалась задача про монеты. Смысл такой - программа должна вычислить минимальное количество банкнот и монет в сумме. -> Пишите - 567 рублей. а программа считает: 500+50+10+5+2.

Задачка очень интересная, но у меня нет навыков, чтобы написать программу.

@кот Бегемот · 28.01.2014, 23:44

Pascal

var
s,n:integer;
begin
readln(s);
n:=0;
n:=n+s div 5000;
s:=s mod 5000;
n:=n+s div 1000;
s:=s mod 1000;
n:=n+s div 500;
s:=s mod 500;
n:=n+s div 100;
s:=s mod 100;
n:=n+s div 50;
s:=s mod 50;
n:=n+s mod 10;
s:=s mod 10;
n:=n+s div 5;
s:=s mod 5;
n:=n+s;
writeln(n);
end.

@ElenaPrg · 29.01.2014, 00:12 **[ТС]**

Syntax error ";", expected but VAR found в первой строчке. открываю код программой Lazarus

@кот Бегемот · 29.01.2014, 00:23

Задача написана на turboPascal, возможно Lazarus требует имя программы, добавьте в начало
program aaa;

@ElenaPrg · 29.01.2014, 00:29 **[ТС]**

Всё равно такая же ошибка.

@кот Бегемот · 29.01.2014, 00:55

К сожалению, я не знаком с синтаксисом Lazarus, на TP всё идёт и выдает ответ, поинтересуйтесь у специалистов в разделе Lazarus

Добавлено через 21 минуту
Опечатка в строке 16. Правильно
n:=n div 10;

Pascal

var
s,n:integer;
begin
readln(s);
n:=0;
n:=n+s div 5000;
s:=s mod 5000;
n:=n+s div 1000;
s:=s mod 1000;
n:=n+s div 500;
s:=s mod 500;
n:=n+s div 100;
s:=s mod 100;
n:=n+s div 50;
s:=s mod 50;
n:=n+s div 10;
s:=s mod 10;
n:=n+s div 5;
s:=s mod 5;
n:=n+s;
writeln(n);
end.

@newyork7776 · 29.01.2014, 02:45

C++

#include<iostream>
using namespace std;
 
void Recur_Search(int sum,int n,int mas[],int &num_min,int num_cur,int mas_ef[],int mas_cur[]);
 
void main()
{
    int mas[100],n,sum;
    cout<<"Enter number = ";cin>>n;
    for(int i=0;i<n;i++)
    {
        cout<<"Enter "<<i+1<<" = ";
        cin>>mas[i];
    }
    cout<<"Suma = ";cin>>sum;
    cout<<"Bankomat = ";
    for(int i=0;i<n;i++)
        cout<<mas[i]<<" ";
    cout<<endl;
    int mas_ef[100],mas_cur[100],num_cur=-1,num_min=100,buf=n-1;
 
    Recur_Search(sum,n-1,mas,num_min,num_cur,mas_ef,mas_cur);
    if(num_min==100)cout<<"No solution";
    else
    {
        cout<<"Number of banknotes = "<<num_min<<endl;
        for(int i=0;i<num_min;i++) cout<<mas_ef[i]<<" ";
    }
    cout<<endl; 
}
 
void Recur_Search(int sum,int n,int mas[],int &num_min,int num_cur,int mas_ef[],int mas_cur[])
{
    if(num_cur!=-1)//начальная проверка - необходима из-за первого входа в рекурсивную процедуру
    {
        sum-=mas[n];//формирование суммы, необходимой для дозаполнения
        mas_cur[num_cur]=mas[n];//добавляем номинал к текущей последовательности
        num_cur++;
    }else num_cur=0;
 
    if(sum==0)//проверка, что необходимую сумму набрали.
    {
        if(num_min>num_cur)
        {//запись новой минимальной последовательности номиналов
            for(int i=0;i<num_cur;i++) mas_ef[i]=mas_cur[i];
            num_min=num_cur;
        }
    }
    else
        if((float(sum)/mas[n])<(num_min-num_cur)) //проверка на возможность добить сумму !!!текущими!!! максимальными купюрами
                //за меньшее количество купюр, чем текущее значение. Иначе возврат на предыдущую итерацию!!!
        {
            while((n>=0)&&(sum<mas[n])) n--;//поиск номинала меньше или равного необходимой суммы
            if(n>=0)//если нашелся необходимый номинал - обрабатываем дальше. Иначе возврат на предыдущую итерацию!!!
            {//последовательно прорабатываем все варианты для номиналов вниз
                for(int i=n;i>=0;i--) Recur_Search(sum,i,mas,num_min,num_cur,mas_ef,mas_cur);
            }
        }
}

valeriikozlov · 29.01.2014, 06:50

Все зависит от того, какой номинал банкнот и монет имеется. В зависимости от этого жадный алгоритм может выдавать неправильные ответы.

@кот Бегемот · 29.01.2014, 09:24

Непонятно, зачем здесь нужна рекурсивная процедура, да ещё на СИ, когда всё просто решается сверху вниз. Можно сделать и циклом.

Pascal

var
a,i,n,s:integer;
begin
readln(s);
n:=0;
a:=5000;
for i:=1 to 8 do
begin
n:=n+s div a;
s:=s mod a;
if i mod 2=1 then a:=a div 5 else a:=a div 2;
end;
writeln(n);
end.

@APALoff · 29.01.2014, 10:33

Pascal

Const
  m : array[1..9] of Integer = (5000,1000,500,100,50,10,5,2,1);
Var
  Money,i : Integer;
  
Procedure tt(n : integer);
Begin
  While Money-n>=0 do
  Begin
    Dec(Money,n);
    Write(n); If Money>0 then write('+');
  End;
End;
 
Begin
  Readln(Money);
  Write(Money,' = ');
  For i:=1 to 9 do tt(m[i]);
  Writeln;
End.

Добавлено через 1 минуту
Это для любых сумм, а не только 3/4-ех значных.

Добавлено через 2 минуты
если нужно именно цифровое значение количества банкнот/монет, то надо будет добавить счетчик между 9-ой и 10-ой строкой.

@кот Бегемот · 29.01.2014, 10:36

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

Pascal

Const
  m : array[1..9] of Integer = (5000,1000,500,100,50,10,5,2,1);
Var
  Money,i : Integer;
  
Procedure tt(n : integer);
Begin
  While Money-n>=0 do
  Begin
    Dec(Money,n);
    Write(n); If Money>0 then write('+');
  End;
End;
 
Begin
  Readln(Money);
  Write(Money,' = ');
  For i:=1 to 9 do tt(m[i]);
  Writeln;
End.

Добавлено через 1 минуту
Это для любых сумм, а не только 3/4-ех значных.

Добавлено через 2 минуты
если нужно именно цифровое значение количества банкнот/монет, то надо будет добавить счетчик между 9-ой и 10-ой строкой.

очень красиво, но количество купюр не считает

@APALoff · 29.01.2014, 10:38

Сообщение от кот Бегемот

очень красиво, но количество купюр не считает

Я же написал где счетчик вставить.

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

Pascal

Const
  m : array[1..9] of Integer = (5000,1000,500,100,50,10,5,2,1);
Var
  Money,i,k : Integer;
  
Procedure tt(n : integer);
Begin
  While Money-n>=0 do
  Begin
    Inc(k);
    Dec(Money,n);
    Write(n); If Money>0 then write('+');
  End;
End;
 
Begin
  k:=0;
  Readln(Money);
  Write(Money,' = ');
  For i:=1 to 9 do tt(m[i]);
  Writeln;
  Writeln('Всего купюр/монет: ',k);
End.

@ElenaPrg · 31.01.2014, 05:25 **[ТС]**

Сообщение от кот Бегемот

var
a,i,n,s:integer;
begin
readln(s);
n:=0;
a:=5000;
for i:=1 to 8 do
begin
n:=n+s div a;
s:=s mod a;
if i mod 2=1 then a:=a div 5 else a:=a div 2;
end;
writeln(n);
end.

а как это изменить, если у меня в стране есть банкноты и монеты такого номинала: 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000?

@APALoff · 31.01.2014, 09:24

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

а как это изменить, если у меня в стране есть банкноты и монеты такого номинала: 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000?

Pascal

Const
  m : array[1..12] of Integer = (5000,2000,1000,500,200,100,50,20,10,5,2,1);
Var
  Money,i,k : Integer;
  
Procedure tt(n : integer);
Begin
  While Money-n>=0 do
  Begin
    Inc(k);
    Dec(Money,n);
    Write(n); If Money>0 then write('+');
  End;
End;
 
Begin
  k:=0;
  Readln(Money);
  Write(Money,' = ');
  For i:=1 to 12 do tt(m[i]);
  Writeln;
  Writeln('Всего купюр/монет: ',k);
End.

@ElenaPrg · 31.01.2014, 09:51 **[ТС]**

APALoff, а какие комментарии можно к этому подписать?

@APALoff · 31.01.2014, 10:10

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

APALoff, а какие комментарии можно к этому подписать?

Ну например:

Отлично работает!

Лучшая программа года!

Простота - залог успеха!

Краткость - сестра таланта!

и т.п.

Добавлено через 57 секунд
а вообще - любые можно написать...

@ElenaPrg · 31.01.2014, 10:21 **[ТС]**

главное зачёт мне получить сегодня) огромнейшее спасибо за программу

программисты не как экономисты - всегда помогают.

@кот Бегемот · 31.01.2014, 16:51

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

главное зачёт мне получить сегодня) огромнейшее спасибо за программу

программисты не как экономисты - всегда помогают.

Беда любой хорошей программы в том, что препод не поверит и заставит объяснять что и как. Поэтому подправлю и свою, примитивную, но имеющую больше шансов прокатить:

Pascal

var
a,i,n,s:integer;
begin
readln(s);
n:=0;
a:=5000;
for i:=1 to 12 do
begin
n:=n+s div a;
s:=s mod a;
if i mod 3=1 then a:=(a*a) div 5 else a:=a div 2;
end;
writeln(n);
end.

Пояснение: последовательно, начиная с самой большой купюры, делим сумму на её номинал , выясняя, сколько таких купюр в сумме, и прибавляем результат к итогу (n:=n+s div a), потом уменьшаем сумму до остатка от деления (s:=s mod a), уменьшаем номинал вдвое или в 2,5 раза (в зависимости от номера операции) и продолжаем всё сначала.

@D7ILeucoH · 26.11.2019, 16:00

Бред, как и почти все решения в этой теме. При номиналах монет в {2,3,4}, ваш алгоритм разобьёт число "5" на что? Правильно, на "4", и всё. Он не сможет догадаться, что есть вариант взять "2 и 3". Он возьмёт один раз "4", и будет искать, где бы ему добить ещё "1". А "1" - нет монеты с таким номиналом.

@mr-Crocodile · 26.11.2019, 16:35

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

Бред, как и почти все решения в этой теме.

вау, вау, полегче..
тема спокойно лежала пять лет, а ты её поднял. и зачем?
затем, чтобы повторить то, что сказано было

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

Все зависит от того, какой номинал банкнот и монет имеется. В зависимости от этого жадный алгоритм может выдавать неправильные ответы.

?

для набора купюр

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

1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000

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

а то, что он не работает на любом наборе данных, так тут ты прав. Но это же вроде никто и не обещал, верно?

@ElenaPrg 1 / 1 / 0 Регистрация: 28.01.2014 Сообщений: 9
	31.01.2014, 05:25 [ТС]	13
	Сообщение от кот Бегемот var a,i,n,s:integer; begin readln(s); n:=0; a:=5000; for i:=1 to 8 do begin n:=n+s div a; s:=s mod a; if i mod 2=1 then a:=a div 5 else a:=a div 2; end; writeln(n); end. а как это изменить, если у меня в стране есть банкноты и монеты такого номинала: 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000? 0

@ElenaPrg 1 / 1 / 0 Регистрация: 28.01.2014 Сообщений: 9
	31.01.2014, 09:51 [ТС]	15
	APALoff, а какие комментарии можно к этому подписать? 0

@ElenaPrg 1 / 1 / 0 Регистрация: 28.01.2014 Сообщений: 9
	31.01.2014, 10:21 [ТС]	17
	главное зачёт мне получить сегодня) огромнейшее спасибо за программу программисты не как экономисты - всегда помогают. 1

@ElenaPrg 1 / 1 / 0 Регистрация: 28.01.2014 Сообщений: 9
	29.01.2014, 00:12 [ТС]	3
	Syntax error ";", expected but VAR found в первой строчке. открываю код программой Lazarus 0

@кот Бегемот Платежеспособный зверь 8834 / 4268 / 1621 Регистрация: 28.10.2009 Сообщений: 11,407
	29.01.2014, 00:23	4
	Задача написана на turboPascal, возможно Lazarus требует имя программы, добавьте в начало program aaa; 1

@ElenaPrg 1 / 1 / 0 Регистрация: 28.01.2014 Сообщений: 9
	29.01.2014, 00:29 [ТС]	5
	Всё равно такая же ошибка. 0

valeriikozlov 4726 / 2547 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	29.01.2014, 06:50	8
	Все зависит от того, какой номинал банкнот и монет имеется. В зависимости от этого жадный алгоритм может выдавать неправильные ответы. 0

@APALoff 1646 / 1075 / 1081 Регистрация: 03.07.2013 Сообщений: 4,507
	31.01.2014, 10:10	16
	Сообщение от ElenaPrg APALoff, а какие комментарии можно к этому подписать? Ну например: Отлично работает! Лучшая программа года! Простота - залог успеха! Краткость - сестра таланта! и т.п. Добавлено через 57 секунд а вообще - любые можно написать... 1

@D7ILeucoH 22 / 20 / 5 Регистрация: 29.02.2016 Сообщений: 590
	26.11.2019, 16:00	19
	Бред, как и почти все решения в этой теме. При номиналах монет в {2,3,4}, ваш алгоритм разобьёт число "5" на что? Правильно, на "4", и всё. Он не сможет догадаться, что есть вариант взять "2 и 3". Он возьмёт один раз "4", и будет искать, где бы ему добить ещё "1". А "1" - нет монеты с таким номиналом. 1

@mr-Crocodile 2931 / 1576 / 630 Регистрация: 19.03.2019 Сообщений: 5,183
	26.11.2019, 16:35	20
	Сообщение от D7ILeucoH Бред, как и почти все решения в этой теме. вау, вау, полегче.. тема спокойно лежала пять лет, а ты её поднял. и зачем? затем, чтобы повторить то, что сказано было Сообщение от valeriikozlov Все зависит от того, какой номинал банкнот и монет имеется. В зависимости от этого жадный алгоритм может выдавать неправильные ответы. ? для набора купюр Сообщение от APALoff 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000 у тебя претензии к представленному алгоритму есть? а то, что он не работает на любом наборе данных, так тут ты прав. Но это же вроде никто и не обещал, верно? 0

Вычислить минимальное количество банкнот и монет в сумме

Решение