Четыре алгоритма поиска наибольшего общего делителя двух чисел в языке C
Цель
1. Уточнить понятие и характеристики алгоритма;
2. На основе анализа проблемы разработайте разумный алгоритм решения проблемы.
Содержание эксперимента
Запустите общий алгоритм наибольшего общего делителя и выполните отладку и тестирование программы. Для этого требуется хороший стиль разработки программы и модуль обработки исключений (например, недопустимый ввод и т. Д.).
Тематический анализ
Чтобы найти наибольший общий делитель двух чисел, обычно используемые алгоритмы включают деление по очереди, исчерпание, дополнительное вычитание, алгоритм Штейна и т. Д. Реализуйте каждый алгоритм с помощью функции, затем используйте оператор switch () в основной функции для вызова любого алгоритма и используйте функции rand () и srand () в основной функции, чтобы сгенерировать случайную функцию для средней операции каждого алгоритма. Испытание временем.
Построение алгоритма
Бросить и разделить
#37. Алгоритм Евклида для нахождения НОД | Python для начинающих
Алгоритм процесса: Предположим, что два числа — это a и b, где a — делимое, b — делитель, а temp — остаток.
1. Поместите большие числа в a и десятичные числа в b;
2. Найдите остаток от a / b;
3. Если temp = 0, b — наибольший общий делитель;
4. Если temp! = 0, присвойте a значение b, а a — значение temp;
5. Вернитесь к шагу 2.
блок-схема
Код
int divisor1 (int a, int b) // Пользовательская функция находит наибольший общий делитель двух чисел < int temp; // Определение целочисленной переменной if (a while (b! = 0) // Найдите остаток от двух чисел в цикле, пока остаток не станет 0 < temp=a%b; a = b; // обмен значениями переменных b=temp; >return (a); // Возвращаем наибольший общий делитель вызывающей функции > // Разделить и разделить (2. Рекурсивный вызов функции) int divisor2(int a,int b) < if (a% b == 0) // Если остаток после взятия остатка от a и b равен 0, вернуть наибольший общий делитель b return b; else return divisor2 (b, a% b); // В противном случае вызовите рекурсивно, продолжаем принимать остаток >
Исчерпывающий метод
Алгоритм процесса: Для двух положительных целых чисел a, b, если целое число temp может быть найдено в интервале [a, 0] или [b, 0] и может делиться как на a, так и на b, то temp является наибольшим общим делителем.
блок-схема
Код
int divisor3(int a,int b) < int temp; temp = (a>b)? b: a; // Использование выражений условной операции для нахождения минимума из двух чисел while(temp>0) < if (a% temp == 0 b% temp == 0) // Пока вы можете найти число, которое может делиться на a и b одновременно, остановите цикл break; temp—; // Если условие if не выполняется, переменная будет уменьшаться до тех пор, пока не станет делиться на a, b >return (temp); >
Больше вычитания
Пишем программу: нахождения НОД и НОК двух чисел | Алгоритм Евклида
Алгоритм процесса: Первый шаг: произвольно дайте два положительных целых числа; оцените, являются ли они оба четными. Если да, используйте 2 для уменьшения; если нет, выполните второй шаг.
Шаг 2. Вычтите меньшее число из большего числа, затем сравните разницу с меньшим числом и уменьшите число на большее число. Продолжайте эту операцию, пока полученный минус и разница не станут равными.
Тогда произведение числа 2, уменьшенного на первом этапе, и среднего числа на втором этапе, является искомым наибольшим общим делителем. «Равное число» — это наибольший общий делитель. Способ найти «равное число» — это метод «большего вычитания». Поэтому метод вычитания more также называется эквивалентным алгоритмом.
блок-схема：
Код
int divisor4(int m,int n) < int i=0,temp,x; while (m% 2 == 0 n% 2 == 0) // Оцениваем, являются ли a и b четными числами, если да, используйте 2 для уменьшения < m/=2; n/=2; i + = 1; // Уменьшаем количество 2 >if (m while (x) // когда x не 0 < x = m-n; // большее число минус меньшее число m = (n>x)? n: x; // Разница больше меньшего числа n = (n if(i==0) return n; else return (int)pow(2,i)*n; >
Алгоритм Штейна
Процесс алгоритма: алгоритм Штейна был предложен Дж. Штейном в 1961 году. Этот метод также вычисляет наибольший общий делитель двух чисел. Наибольший общий делитель имеет следующие свойства: gcd (kx,ky) = k * gcd (x, y) такое очень хорошее свойство. Попробуйте взять k = 2, затем gcd (2x, 2y) = 2 * gcd (x, y). Быстро подумайте о способе уменьшения двух четных чисел для двух целых положительных чисел x> y:
1. Все четные числа gcd (x, y) = 2gcd (x / 2, y / 2);
2. Все нечетные gcd (x, y) = gcd ((x + y) / 2, (x-y) / 2);
2. x нечетный y четный gcd (x, y) = gcd (x, y / 2);
3. x четный y нечетный gcd (x, y) = gcd (x / 2, y) или gcd (x, y) = gcd (y, x / 2);
Теперь, когда у нас есть рекурсивная формула, нам нужно найти другое вырождение. Обратите внимание, что gcd (x, x) = x, просто используйте это.
блок-схема：
Код：
int Stein(int x,int y) < int factor=0; int temp; if(xif(y==0) return 0; // 0 может делиться на любое ненулевое число while(x!=y) < if (x if (y y=(x-y)>>1; x=x-y; > else < y >> = 1; // x нечетное, y четное > > else < if (y x>>=1; if(x > else // x, y четные < x>>=1; y>>=1; ++factor; > > > return (x
Исходный код
#include #include #include // Заголовочный файл Pow (2, i) #include // Заголовочный файл для расчета времени работы программы и случайно сгенерированных чисел // Разделить и разделить (1. Вложенный вызов функции) int divisor1 (int a, int b) // Пользовательская функция находит наибольший общий делитель двух чисел < int temp; // Определение целочисленной переменной if (a while (b! = 0) // Найдите остаток от двух чисел в цикле, пока остаток не станет 0 < temp=a%b; a = b; // обмен значениями переменных b=temp; >return (a); // Возвращаем наибольший общий делитель вызывающей функции > // Разделить и разделить (2.
Рекурсивный вызов функции) int divisor2(int a,int b) < if (a% b == 0) // Если остаток после взятия остатка от a и b равен 0, вернуть наибольший общий делитель b return b; else return divisor2 (b, a% b); // В противном случае вызовите рекурсивно, продолжаем принимать остаток >// Исчерпывающий метод int divisor3(int a,int b) < int temp; temp = (a>b)? b: a; // Использование выражений условной операции для нахождения минимума из двух чисел while(temp>0) < if (a% temp == 0 b% temp == 0) // Пока вы можете найти число, которое может делиться на a и b одновременно, остановите цикл break; temp—; // Если условие if не выполняется, переменная будет уменьшаться до тех пор, пока не станет делиться на a, b >return (temp); > // Еще метод вычитания int divisor4(int m,int n) < int i=0,temp,x; while (m% 2 == 0 n% 2 == 0) // Оцениваем, являются ли a и b четными числами, если да, используйте 2 для уменьшения < m/=2; n/=2; i + = 1; // Уменьшаем количество 2 >if (m while (x) // когда x не 0 < x = m-n; // большее число минус меньшее число m = (n>x)? n: x; // Разница больше меньшего числа n = (n if(i==0) return n; else return (int)pow(2,i)*n; > // алгоритм Штейна int Stein(int x,int y) < int factor=0; int temp; if(xif(y==0) return 0; // 0 может делиться на любое ненулевое число while(x!=y) < if (x if (y y=(x-y)>>1; x=x-y; > else < y >> = 1; // x нечетное, y четное > > else < if (y x>>=1; if(x > else // x, y четные < x>>=1; y>>=1; ++factor; > > > return (x <void main() < int x,y,temp; int m,n,p,i,N,s[100]; printf(«—————You have two options————-n»); printf («1. Операция нахождения наибольшего общего делителя двух чисел n»); printf («2.
Рассчитать время работы программы и операцию проверки случайных чисел n»); printf(«————————————————n»); printf(«Please input a number you want:n «); scanf(«%d», if(n<1||n>2) < printf(«error! Please input again!n»); scanf(«%d», >if(n==1) < printf («Пожалуйста, введите два положительных целых числа (через запятую): n»); scanf(«%d,%d»,y); printf(«There are five ways to find the greatest common divisor,you can choose one:n»); printf («—————— Выбрать метод ——————- n»); printf («1.
Разделить и разделить (вложенный вызов функции) n»); printf («2. Перебросить и разделить (рекурсивный вызов функции) n»); printf («3. Исчерпывающий метод n»); printf («4.
Еще метод уменьшения фазы n»); printf («Алгоритм 5.Штейна n»); printf(«———————————————n»); while(1) < printf(«Please input the way of you choice:n»); scanf(«%d», switch(m) < case 1: printf («Сначала вы выбираете (первый выбираете) n»); temp=divisor1(x,y); printf(«The greatest common divisor is %dn»,temp); break; case 2: printf («Ваш выбор второй (ваш выбор второй) n»); temp=divisor2(x,y); printf(«The greatest common divisor is %dn»,temp); break; case 3: printf («Ваш выбор третий (Исчерпывающий метод) n»); temp=divisor3(x,y); printf(«The greatest common divisor is %dn»,temp); break; case 4: printf («Ваш выбор — четвертый (больше метод уменьшения фазы) n»); temp=divisor4(x,y); printf(«The greatest common divisor is %dn»,temp); break; case 5: printf («Ваш выбор пятый (алгоритм Штейна) n»); temp=Stein(x,y); printf(«The greatest common divisor is %dn»,temp); break; >> > else if(n==2) < clock_t start,finish; double T; srand((unsigned)time(NULL)); printf («Сколько наборов данных вы хотите протестировать: n»); scanf(«%d», for(i=0;iprintf(«n»); printf («Есть пять способов найти наибольший общий делитель, вы можете выбрать один: n»); // Выбрать меню printf («—————— Выбрать метод ——————- n»); printf («1. Разделить и разделить (вложенный вызов функции) n»); printf («2.
Перебросить и разделить (рекурсивный вызов функции) n»); printf («3. Исчерпывающий метод n»); printf («4. Еще метод уменьшения фазы n»); printf («Алгоритм 5.Штейна n»); printf(«———————————————n»); while(1) < int j=0; printf(«Please input the way of you choice:n»); scanf(«%d», while(p<1||p>5) < printf («Ошибка ввода! Пожалуйста, введите повторно: n»); scanf(«%d», >switch(p) < case 1: start = clock (); // Программа запускается, время старта while(jfinish = clock (); // Программа окончена, отсчет времени закончился break; case 2: start=clock(); while(j finish=clock(); break; case 3: start=clock(); while(j finish=clock(); break; case 4: start=clock(); while(j finish=clock(); break; case 5: start=clock(); while(j finish=clock(); break; > T = (double) (finish-start) / 1000; // Вычислить разницу во времени. Поскольку компьютер считает миллисекунды, она конвертируется в секунды и делится на 1000 printf («Время работы этого метода% f секунд n», T); > > >
Результаты отладки, тестирования и запуска
результат операции 
Результат отладки 
Время выполнения теста 
Резюме опыта
Возникшие проблемы
1. Я плохо разбирался в алгоритме Штейна. Я не понял программу после прочтения программы, но, подумав, мне все еще нужно разобраться в ней, поэтому я проверил много информации по csdn. Я посоветовался с окружающими меня учениками и, наконец, выяснил этот алгоритм.
2. Для сравнения времени работы четырех алгоритмов при разных масштабах тестовых данных я сначала не подумал об использовании случайной функции для генерации данных, но я хотел ввести ее вручную. Очевидно, что у этого подхода есть ограничения, и много информации также упоминается для случайных функций.
подводить итоги
Условно говоря, первые два метода относительно просты и легки для понимания. Последние два алгоритма требуют обдумывания и проверки информации. Что касается третьего метода, я Я хочу сделать следующее: можно ли не судить, являются ли два числа четными, и напрямую уменьшать число в цикле до тех пор, пока два числа не станут равными. Я сам пробовал, и действительно можно найти наибольший общий делитель, и это относительно просто и легко понять. Поэтому я думаю, что в этом примере ответ на каждый вопрос не должен быть уникальным, и мы должны набраться смелости, чтобы попробовать новые методы.
Источник: russianblogs.com
Написать программу, которая вычисляет наибольший общий делитель двух целых чисел
Найди верный ответ на вопрос ✅ «Написать программу, которая вычисляет наибольший общий делитель двух целых чисел Паскаль . » по предмету Информатика, а если ответа нет или никто не дал верного ответа, то воспользуйся поиском и попробуй найти ответ среди похожих вопросов.
Новые вопросы по информатике
Сколько всего различных символов может быть в восьмибитной текстовой кодировке? 1) 8 2) 512 3) 256 4) 65536
Паскаль. Написать программу подсчета количества отрицательных чисел среди любых 10 вводимых. 1 программа с использованием while, 2 программа — repeat
Сколько кб информации содержит сообщение объемом 2^20 бит?
Информатика пользователь создад сообщение из 256 символов в кодировке Unicode в которой каждый символ кодируется 16 битами после редактирования информационный объем сообщения составил 3072 бит Определите сколько символов удалили сообщение если его
Запишите числа в беззнаковом коде (формат 1 байт): а) 31; б) 163; в) 65; г) 128.
Главная » Информатика » Написать программу, которая вычисляет наибольший общий делитель двух целых чисел Паскаль
Источник: urokam.net