Разработайте блок-схему для нахождения алгоритма Евклида.
Дескриптор Обучающийся
- использует блок ввода и вывода;
- использует оператор присваивания;
- использует циклическую структуру;
- использует структуру ветвления;
- определяет условие в структуре цикла и ветвления.
Воспользуемся расширенной записью числа
87=an²+bn+2 → an²+bn-85=0
Известно, что если многочлен с целочисленными коэффициентами имеет хотя бы один вещественный корень, то он находится среди делителей свободного члена. Нас интересуют только натуральные делители, большие 2, поскольку n - основание системы счисления и в этой системе имеется цифра 2.
85 = 5 × 17. Число 17 не подходит, потому что 17>10 и двухзначное десятичное число в системе счисления с основанием, большим 10, не может иметь в записи больше двух знаков. Следовательно, n=5.
Для проверки переводим 87 в систему счисления по основанию 5.
87 / 5 = 17, остаток 2
17 / 5 = 3, остаток 2
3 / 5 = 0, остаток 3.
Выписываем остатки в обратном порядке: 322
87₁₀ = 322₅ - в числе три разряда и оно оканчивается двойкой.
ответ: N=5
#include <iostream>
using namespace std;
int k=2;
bool StrangeSeq(int n){
if (k<n){
if(n%k==0){
cout<<"false";
return false;
}
k++;
StrangeSeq(n);
}
else
{
cout<<"true";
return true;
}
}
int main(){
int n;
cin>>n;
StrangeSeq(n);
cin.get();
cin.get();
}