Python使用窮舉法求兩個(gè)數(shù)的最大公約數(shù)問題

更新時(shí)間：2022年12月20日 11:16:52 作者：半島鐵盒@

這篇文章主要介紹了Python使用窮舉法求兩個(gè)數(shù)的最大公約數(shù)問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

使用窮舉法求兩個(gè)數(shù)的最大公約數(shù)

for m in range (0,2):
    a = int(input("請(qǐng)輸入一個(gè)數(shù):"))
    b = int(input("請(qǐng)輸入另外一個(gè)數(shù):"))
    #判斷num1與num2的大小
    if a > b:
        #獲取最小值
        min = b
    else:
        #獲取最小值
        min = a
    for i in range(min+1,0,-1):    #倒序
        #滿足公因數(shù)的條件:
        if (a % i == 0) and (b % i == 0):
            c = i
            break
    print('這兩個(gè)數(shù)的最大公約數(shù)是:%d '%c)

窮舉法求N個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)

基本要求

求N個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)。用C或C++或java或python語言實(shí)現(xiàn)程序解決問題。

提高要求

思考一個(gè)“求公約數(shù)”和“求公倍數(shù)”之類問題的“逆問題”，這個(gè)問題是這樣的：已知正整數(shù)a0,a1,b0,b1，設(shè)某未知正整數(shù)x滿足：

1、x和a0的最大公約數(shù)是a1；
2、x和b0的最小公倍數(shù)是b1。

Hankson的“逆問題”就是求出滿足條件的正整數(shù)x。但稍加思索之后，他發(fā)現(xiàn)這樣的x并不唯一，甚至可能不存在。因此他轉(zhuǎn)而開始考慮如何求解滿足條件的x的個(gè)數(shù)。

輸入格式

輸入第一行為一個(gè)正整數(shù)n，表示有n組輸入數(shù)據(jù)。接下來的n行每行一組輸入數(shù)據(jù)，為四個(gè)正整數(shù)a0，a1，b0，b1，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開。輸入數(shù)據(jù)保證a0能被a1整除，b1能被b0整除。

輸出格式

輸出共n行。每組輸入數(shù)據(jù)的輸出結(jié)果占一行，為一個(gè)整數(shù)。
對(duì)于每組數(shù)據(jù)：若不存在這樣的x，請(qǐng)輸出0；
若存在這樣的x，請(qǐng)輸出滿足條件的x的個(gè)數(shù)；

樣例輸入

2

41 1 96 288

95 1 37 1776

算法設(shè)計(jì)思路

本程序先用窮舉法計(jì)算兩個(gè)數(shù)的最大公約數(shù)或最小公倍數(shù)。從兩個(gè)數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù) 。

①定義1：對(duì)兩個(gè)正整數(shù)a,b如果能在區(qū)間[a,0]或[b,0]內(nèi)能找到一個(gè)整數(shù)temp能同時(shí)被a和b所整除，則temp即為最大公約數(shù)。

②定義2：對(duì)兩個(gè)正整數(shù)a,b,如果若干個(gè)a之和或b之和能被b所整除或能被a所整除，則該和數(shù)即為所求的最小公倍數(shù)。

#include<stdio.h>
#define N 1000 ?/*自定義數(shù)組長(zhǎng)度*/
int input(int t[])
{
?? ?int i,n;
?? ?int k=1;
?? ?printf("Please input the count of numbers(n>=2):"); /*輸入計(jì)算值的個(gè)數(shù)*/
?? ?scanf("%d",&n);
?? ?while(k)
?? ?{
?? ??? ?printf("Please input numbers:\n"); ?/*輸入所算值*/
?? ??? ?for(i=0;i<n;i++)
?? ??? ?{
?? ??? ??? ?scanf("%d",&t[i]);
?? ??? ?}
?? ??? ?k=exper(t,n);
?? ?}
?? ?return n;
}
int exper(int t[],int n) ? /*驗(yàn)證函數(shù)*/
{
?? ?int i;
?? ?for(i=0;i<n;i++)
?? ?{
?? ??? ?if(!t[i])
?? ??? ?{
?? ??? ??? ?printf("error(輸入為0)\n");
?? ??? ??? ?return 1;
?? ??? ?}
?? ?}
? ?return 0;
}
int divisor (int a,int b) /*自定義函數(shù)求兩數(shù)的最大公約數(shù)*/
{
? ? int ?temp; ? ? ? ? ?/*定義義整型變量*/
? ? temp=(a>b)?b:a; ? ?/*采種條件運(yùn)算表達(dá)式求出兩個(gè)數(shù)中的最小值*/
? ? while(temp>0)
? ? {
? ? ? ?if (a%temp==0&&b%temp==0) /*只要找到一個(gè)數(shù)能同時(shí)被a,b所整除，則中止循環(huán)*/
? ? ? ? ? break;
? ? ? ?temp--; ? ? ?/*如不滿足if條件則變量自減，直到能被a,b所整除*/
? ? }
? return (temp); /*返回滿足條件的數(shù)到主調(diào)函數(shù)處*/
}
int Gcd(int t[],int n)
{
?? ?int i;
?? ?int c=t[0];
?? ?for(i=1;i<n;i++)
?? ?{
?? ??? ?c=divisor(c,t[i]); ?/*求N個(gè)數(shù)的最大公約數(shù)*/
?? ?}
?? ?return c;
}
int multiple (int a,int b)
{
? int p,q,temp;
? p=(a>b)?a:b; ? /*求兩個(gè)數(shù)中的最大值*/
? q=(a>b)?b:a; ?/*求兩個(gè)數(shù)中的最小值*/
? temp=p; ? ? ?/*最大值賦給p為變量自增作準(zhǔn)備*/
? while(1) ??
? {
? ? if(p%q==0)
? ? ? break; ?/*只要找到變量的和數(shù)能被a或b所整除，則中止循環(huán)*/
? ? p+=temp; ? /*如果條件不滿足則變量自身相加*/
? }
? return ?(p);
}
int Mul(int t[],int n)
{
?? ?int i;
?? ?int s=t[0];
?? ?for(i=0;i<n;i++)
?? ?{
?? ??? ?s=multiple(s,t[i]); ?/*求N個(gè)數(shù)的最小公倍數(shù)*/
?? ?}
?? ?return s;
}
int main()
{
?int t[N];
?int n;
?int flag=1;
?while(flag)
?{
? ? n=input(t);
? ? printf("The higest common divisor is %d\n",Gcd(t,n)); ?/*輸出最大公約數(shù)*/
? ? printf("The lowest common multiple is %d\n",Mul(t,n));/*輸出最小公倍數(shù)*/
? ? printf("retreat:press 0\ncontiune:press 1");
? ? scanf("%d",&flag);
?}
?return 0;
}