Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.80
Арслан94
0 / 0 / 0
Регистрация: 05.03.2013
Сообщений: 15
#1

Написать программу для нахождения НОД двух произвольных целых чисел - C++

05.03.2013, 19:09. Просмотров 1940. Ответов 10
Метки нет (Все метки)

1. Написать программу для нахождения НОД двух произвольных целых чисел.
2. Написать программу для проверки произвольного целого числа на простоту.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.03.2013, 19:09     Написать программу для нахождения НОД двух произвольных целых чисел
Посмотрите здесь:

Используя функцию нахождения НОД двух натуральных чисел, сократить обычную дробь C++
C++ Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел
C++ Написать шаблоны функций для для вычисления суммы произведений двух соседних чисел для трех целых чисел и в одномерном массиве целых чисел
Написать программу для нахождения НОД многочленов C++
C++ Найти НОД двух целых чисел
C++ Написать функцию, определяющую НОД(наибольший общий делитель) двух целых чисел
C++ Составить программу для нахождения наименьшего общего делителя двух целых чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mysterion777
 Аватар для Mysterion777
-74 / 48 / 2
Регистрация: 11.01.2013
Сообщений: 199
05.03.2013, 19:16     Написать программу для нахождения НОД двух произвольных целых чисел #2
НОД
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
#include <iostream>
using namespace std;
int a,b;
 
int main(){
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  cin>>a>>b;
  while(b) b^=a^=b^=a%=b;
  cout<<a;
  return 0;
}
а на простоту множество алгоритмов Соловея-Штрасена и другие но тебе нужен НУБОВЫЙ легкий алго такой
C++
1
2
for(i=2;i<sqrt(n);i++)if(n%i==0){cout<<"составное";return 0;}
cout<<простое;
fuelcs
12 / 12 / 0
Регистрация: 23.01.2013
Сообщений: 143
05.03.2013, 20:10     Написать программу для нахождения НОД двух произвольных целых чисел #3
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
#include <iostream>
using namespace std;
 
int main()
{
    int a,b,a1,b1,r;
    r=1;
    cout << "Pervoe chislo = ";
    cin >> a;
    cout << "Vtoroe chislo = ";
    cin >> b;
    if (a<b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
    a1=a;
    b1=b;
    while(r!=0)
    {
        for (int i=1;;i++)
        {
            r=a1-b1*i;
            if (r==0)
                break;
            if (r<b1)
            {
                cout << a1 << "=" << i << "*" << b1 << "+" << r << "\n";
                a1=b1;
                b1=r;
                break;
            }
        }
    }
    cout << "NOD(" << a << "," << b << ") = " << b1;
    return 0;
}
Добавлено через 24 минуты
Mysterion777, подскажите пожалуйста как работает:
C++
1
b^=a^=b^=a%=b;
?
Пaтрик
 Аватар для Пaтрик
395 / 388 / 38
Регистрация: 21.01.2012
Сообщений: 972
Завершенные тесты: 1
05.03.2013, 20:16     Написать программу для нахождения НОД двух произвольных целых чисел #4
Переменной a присваивается остаток от деления a на b, и последующий своп.
fuelcs
12 / 12 / 0
Регистрация: 23.01.2013
Сообщений: 143
05.03.2013, 20:21     Написать программу для нахождения НОД двух произвольных целых чисел #5
Пaтрик, я не совсем понял... там три оператора (Присваивание с побитовым исключающим ИЛИ)...
если вас не затруднит...
Пaтрик
 Аватар для Пaтрик
395 / 388 / 38
Регистрация: 21.01.2012
Сообщений: 972
Завершенные тесты: 1
05.03.2013, 20:33     Написать программу для нахождения НОД двух произвольных целых чисел #6
fuelcs, http://ideone.com/ZztIGL
Фишка стара как этот мир, обмен значениями двух переменных без использования третьей переменной.
Mysterion777
 Аватар для Mysterion777
-74 / 48 / 2
Регистрация: 11.01.2013
Сообщений: 199
05.03.2013, 20:37     Написать программу для нахождения НОД двух произвольных целых чисел #7
ну это свойство операции ксор такое если её 2 раза подряд применить то типо свап получается
101---1 число
тут ксор
010---2 число
111-результат
тут ксор
101--2 числооо
010--опять первое
fuelcs
12 / 12 / 0
Регистрация: 23.01.2013
Сообщений: 143
05.03.2013, 20:54     Написать программу для нахождения НОД двух произвольных целых чисел #8
Mysterion777, а насколько оно быстрое? можно, например, это использовать при сортировке массивов?
Mysterion777
 Аватар для Mysterion777
-74 / 48 / 2
Регистрация: 11.01.2013
Сообщений: 199
05.03.2013, 21:17     Написать программу для нахождения НОД двух произвольных целых чисел #9
можно, ну я думаю прям большого прироста производительности не будет, а так хорошая идея)))
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.03.2013, 22:13     Написать программу для нахождения НОД двух произвольных целых чисел #10
Цитата Сообщение от fuelcs Посмотреть сообщение
Mysterion777, а насколько оно быстрое?
Оно медленное. Помимо всех тех же операций присваивания получаем еще и ксоры.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.03.2013, 08:18     Написать программу для нахождения НОД двух произвольных целых чисел
Еще ссылки по теме:

Составить программу для нахождения наименьшего общего делителя двух целых чисел! C++
Написать программу , которая для двух одномерных массивов целых чисел выводит только те элементы C++
Изучение алгоритмов для нахождения НОД целых чисел C++
Написать программу, вычисляющую НОД (наибольший общий делитель) двух целых чисел C++
Найти НОД двух целых чисел по алгоритму Евклида. C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Арслан94
0 / 0 / 0
Регистрация: 05.03.2013
Сообщений: 15
08.03.2013, 08:18  [ТС]     Написать программу для нахождения НОД двух произвольных целых чисел #11
спасибо всем
Yandex
Объявления
08.03.2013, 08:18     Написать программу для нахождения НОД двух произвольных целых чисел
Ответ Создать тему
Опции темы

Текущее время: 05:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru