Помогите с задачей

[grizzzlly]

Вечер добрый. Подскажите хотя бы алгоритм.
Игровой автомат принимает монеты только двух видом а рублей и b рублей. У игрока имеется неограниченный набор монет а и b, Удастся ли набрать s рублей, без сдачи. s,a,b вводятся пользователем.

[p51x]

Берете максимальное из а и б. Делите с на максимум с остатком. Берете остаток и делите на меньшее, если остаток 0, то набрали. Годится?

[grizzzlly]

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

Берете максимальное из а и б. Делите с на максимум с остатком. Берете остаток и делите на меньшее, если остаток 0, то набрали. Годится?

К сожалению не все так просто. Например с = 57, а =5, б=7. Максимум 7, 57 mod 7 = 1, 1 mod 5 !=0

[Аватар]

В цикле начиная с ноль монет любого достоинства до тех пор пока или их сумма превысит s, или остаток s делится нацело на монету другого достоинства. Насчет оптимальности не думал, может решение p51x по другому сформировать и будет сильно оптимальней

[p51x]

К сожалению не все так просто.

Ну значит надо делать и для второго числа. Сделать параллельно и все.

[Аватар]

Так не получится. Вообще-то это диофантово уравнение первой степени с двумя неизвестными и сводится к нахождению НОД а и b, и если этот НОД является делителем s, то все ok, иначе неудача. Насколько нахождение НОД оптимальней цикла предложенного в #4 пусть ТС разбирается

И тоже не совсем так - так показывается, что есть решение в целых числах, в том числе и отрицательных. А нужно показать факт существования решения в неотрицательных числах

[Gekan]

Примерно так можно.

#include <iostream>
using namespace std;

void main()
{
	setlocale(0,"");
	int s=55, x=5, y=7;
	cout<<"s = "<<s<<endl;
	cout<<"x = "<<x<<endl;
	cout<<"y = "<<y<<endl;
	int m = max(x,y)/min(x,y);
	int n = max(x,y) % min(x,y);	
        //чуть сокращаем время
        if (n==0)
	{
		if (s%min(x,y)!=0)
			cout<<"Не удастся набрать " <<s<<" рублей"<<endl;
		else
			cout<<"Удастся набрать " <<s<<" рублей"<<endl;
		return;
	}
	for (int i=0; i<=s/x;i++)
		for (int j=0; j<=s/y;j++)
			if (i*x+j*y==s)
			{
				cout<<"Удастся набрать " <<s<<" рублей"<<endl;
				return;
			}
	cout<<"Не удастся набрать " <<s<<" рублей"<<endl;
}