Получение одного числа из другого с помощью арифметических операций

@Asenaa · Регистрация: 07.10.2017

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

Уважаемые форумчане.Нужна ваша помощь.Не могу решить задачу,ибо туп.
Дано:
Определить можно ли с использованием только операций «прибавить 3» и «прибавить 5» получить из числа 1 число N (N - натуральное, не превышает 106). Разумеется, само число 1 получить можно, просто не применяя никаких операций.

Входные данные:
Вводится число N.

Выходные данные
:Выведите слово YES, если число N можно получить из числа 1, или NO - в противном случае.

Ниже мой код.Не знаю,что дальше делать,то есть саму рекурсивную функцию написать не могу

C++

#include <iostream>
using namespace std;
int result;
int can(int n)
{
    if(n==1){return 1;}
    result=????
    return result;
}
 
int main()
{
int n;
cin>>n;
if(can(n)==1){cout<<"YES";}
else {cout<<"NO";}
return 0;
}

Добавлено через 11 минут
Задачу решить надо с помощью рекурсии

@oldnick85 · 07.10.2017, 16:29

Попробуйте такой вариант:

C++

bool can(int n)
{
  if (n < 0)
    return false
  elif (n == 0)
    return true
  else
    return (can(n-3) || can(n-5))
}

Только вызывать её нужно не для n, а для n-1 в вашем случае:

C++

int main()
{
  int n;
  cin >> n;
  if (can(n-1))
    cout << "YES";
  else 
    cout << "NO";
  return 0;
}

@Asenaa · 07.10.2017, 16:38 **[ТС]**

Спасибо большое.Все работает.Осталось код понять

@oldnick85 · 07.10.2017, 16:52

Чтобы понять рекурсию нужно понять рекурсию

Asenaa, Вам точно нужно с помощью рекурсии было сделать? Это, пожалуй, самое неоптимальное решение для данной задачи.
ЗЫ: Да, и не кормите функцию большими значениями, а то стек забьётся и программа упадёт.
ЗЗЫ: И return (can(n-3) || can(n-5)) лучше поменять на return (can(n-5) || can(n-3)), так должно немного быстрее работать.

@Asenaa · 07.10.2017, 17:26 **[ТС]**

Да я понял рекурсию.Просто этот тип bool я вообще не понимаю.Вот так переписал код для себя.

C++

#include <iostream>
using namespace std;
int can(int n)
{
  if (n < 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return (can(n-3) || can(n-5));
}
int main()
{
  int n;
  cin >> n;
  if (can(n)==1)
    cout << "YES";
  else 
    cout << "NO";
  return 0;
}

@COKPOWEHEU · 07.10.2017, 17:48

А ведь достаточно было одного цикла...

C

1 2	for(b=0; b<=N; b+=5)if( (N-1-b)%3 == 0)return 1; return 0;

@oldnick85 · 07.10.2017, 19:43

Можно и вообще без циклов и рекурсий тогда уж.
Задача сводится к разрешимости линейного диофантова уравнения с двумя переменными. Действительно, требуется выяснить найдутся ли два таких натуральных числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?x$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?y$ , что будет выполняться равенство $https://www.cyberforum.ru/cgi-bin/latex.cgi?1+3\cdot x+5\cdot y=n$ , что можно переписать как
$https://www.cyberforum.ru/cgi-bin/latex.cgi?3\cdot x+5\cdot y=n-1=c.$
Решая это уравнение получим его общее решение:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x_t=27\cdot c-5\cdot t;$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y_t=-16\cdot c+3\cdot t.$
Так как нам для решения требуются $https://www.cyberforum.ru/cgi-bin/latex.cgi?x_t\geq 0$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?y_t\geq 0$ , то решаем систему неравенств
$https://www.cyberforum.ru/cgi-bin/latex.cgi?27\cdot c-5\cdot t\geq 0;$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?-16\cdot c+3\cdot t\geq 0.$
Итого:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{16}{3}\cdot c\leq t \leq\frac{27}{5}\cdot c$
или
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{16}{3}\cdot (n-1)\leq t \leq\frac{27}{5}\cdot (n-1)$ ,
при этом $https://www.cyberforum.ru/cgi-bin/latex.cgi?t$ должно быть целым числом.
Короче просто достаточно проверить, что между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{16}{3}\cdot (n-1)$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{27}{5}\cdot (n-1)$ (включительно) есть целые числа.

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

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

Просто этот тип bool я вообще не понимаю

Тип bool это логический тип, принимает два значения: true и false, которые можно трактовать как "да" и "нет" или как "не ноль" и "ноль" (но, хотя C и позволяет, лучше не мешать логические значения и числовые). То есть если функция возвращает bool, то она как бы отвечает на вопрос "да" или "нет". Представьте, что вместо функции can(n) написано "Разложимо n?", а её результат - "да", если true и "нет", если false.

@Asenaa 0 / 0 / 0 Регистрация: 07.10.2017 Сообщений: 4
	07.10.2017, 16:38 [ТС]	3
	Спасибо большое.Все работает.Осталось код понять 0

@oldnick85 36 / 34 / 10 Регистрация: 15.07.2017 Сообщений: 126
	07.10.2017, 16:52	4
	Чтобы понять рекурсию нужно понять рекурсию Asenaa, Вам точно нужно с помощью рекурсии было сделать? Это, пожалуй, самое неоптимальное решение для данной задачи. ЗЫ: Да, и не кормите функцию большими значениями, а то стек забьётся и программа упадёт. ЗЗЫ: И return (can(n-3) \|\| can(n-5)) лучше поменять на return (can(n-5) \|\| can(n-3)), так должно немного быстрее работать. 0

@oldnick85 36 / 34 / 10 Регистрация: 15.07.2017 Сообщений: 126
	07.10.2017, 19:43	7
	Можно и вообще без циклов и рекурсий тогда уж. Задача сводится к разрешимости линейного диофантова уравнения с двумя переменными. Действительно, требуется выяснить найдутся ли два таких натуральных числа $https://www.cyberforum.ru/cgi-bin/latex.cgi?x$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?y$ , что будет выполняться равенство $https://www.cyberforum.ru/cgi-bin/latex.cgi?1+3\cdot x+5\cdot y=n$ , что можно переписать как $https://www.cyberforum.ru/cgi-bin/latex.cgi?3\cdot x+5\cdot y=n-1=c.$ Решая это уравнение получим его общее решение: $https://www.cyberforum.ru/cgi-bin/latex.cgi?x_t=27\cdot c-5\cdot t;$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?y_t=-16\cdot c+3\cdot t.$ Так как нам для решения требуются $https://www.cyberforum.ru/cgi-bin/latex.cgi?x_t\geq 0$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?y_t\geq 0$ , то решаем систему неравенств $https://www.cyberforum.ru/cgi-bin/latex.cgi?27\cdot c-5\cdot t\geq 0;$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?-16\cdot c+3\cdot t\geq 0.$ Итого: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{16}{3}\cdot c\leq t \leq\frac{27}{5}\cdot c$ или $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{16}{3}\cdot (n-1)\leq t \leq\frac{27}{5}\cdot (n-1)$ , при этом $https://www.cyberforum.ru/cgi-bin/latex.cgi?t$ должно быть целым числом. Короче просто достаточно проверить, что между $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{16}{3}\cdot (n-1)$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{27}{5}\cdot (n-1)$ (включительно) есть целые числа. Добавлено через 11 минут Сообщение от Asenaa Просто этот тип bool я вообще не понимаю Тип bool это логический тип, принимает два значения: true и false, которые можно трактовать как "да" и "нет" или как "не ноль" и "ноль" (но, хотя C и позволяет, лучше не мешать логические значения и числовые). То есть если функция возвращает bool, то она как бы отвечает на вопрос "да" или "нет". Представьте, что вместо функции can(n) написано "Разложимо n?", а её результат - "да", если true и "нет", если false. 1

Получение одного числа из другого с помощью арифметических операций

Решение