Python使用穷举法求两个数的最大公约数问题
作者:半岛铁盒@ 发布时间:2022-01-20 21:26:51
使用穷举法求两个数的最大公约数
for m in range (0,2):
a = int(input("请输入一个数:"))
b = int(input("请输入另外一个数:"))
#判断num1与num2的大小
if a > b:
#获取最小值
min = b
else:
#获取最小值
min = a
for i in range(min+1,0,-1): #倒序
#满足公因数的条件:
if (a % i == 0) and (b % i == 0):
c = i
break
print('这两个数的最大公约数是:%d '%c)
穷举法求N个数的最大公约数和最小公倍数
基本要求
求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。
提高要求
思考一个“求公约数”和“求公倍数”之类问题的“逆问题”,这个问题是这样的:已知正整数a0,a1,b0,b1,设某未知正整数x满足:
1、x和a0的最大公约数是a1;
2、x和b0的最小公倍数是b1。
Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后,他发现这样的x并不唯一,甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。
输入格式
输入第一行为一个正整数n,表示有n组输入数据。接下来的n行每行一组输入数据,为四个正整数a0,a1,b0,b1,每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除,b1能被b0整除。
输出格式
输出共n行。每组输入数据的输出结果占一行,为一个整数。
对于每组数据:若不存在这样的x,请输出0;
若存在这样的x,请输出满足条件的x的个数;
样例输入
2
41 1 96 288
95 1 37 1776
算法设计思路
本程序先用穷举法计算两个数的最大公约数或最小公倍数。从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。
①定义1:对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除,则temp即为最大公约数。
②定义2:对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除,则该和数即为所求的最小公倍数。
#include<stdio.h>
#define N 1000 /*自定义数组长度*/
int input(int t[])
{
int i,n;
int k=1;
printf("Please input the count of numbers(n>=2):"); /*输入计算值的个数*/
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) /*验证函数*/
{
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) /*自定义函数求两数的最大公约数*/
{
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 Gcd(int t[],int n)
{
int i;
int c=t[0];
for(i=1;i<n;i++)
{
c=divisor(c,t[i]); /*求N个数的最大公约数*/
}
return c;
}
int multiple (int a,int b)
{
int p,q,temp;
p=(a>b)?a:b; /*求两个数中的最大值*/
q=(a>b)?b:a; /*求两个数中的最小值*/
temp=p; /*最大值赋给p为变量自增作准备*/
while(1)
{
if(p%q==0)
break; /*只要找到变量的和数能被a或b所整除,则中止循环*/
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个数的最小公倍数*/
}
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)); /*输出最大公约数*/
printf("The lowest common multiple is %d\n",Mul(t,n));/*输出最小公倍数*/
printf("retreat:press 0\ncontiune:press 1");
scanf("%d",&flag);
}
return 0;
}
测试截屏
输入数据正确时:
输入数据有0时会提示错误,计算完成后可以退出和继续:
来源:https://blog.csdn.net/weixin_45556441/article/details/123733406
猜你喜欢
- 在这个擦亮自己的眼睛去看SQL Server的系列中的第二篇中提过要写历史渊源,这里的历史主要描述的是数据库本身的历史与SQL Server
- 单线程+多任务异步协程协程在函数(特殊函数)定义的时候,使用async修饰,函数调用后,内部语句不会立即执行,而是会返回一个协程对象任务对象
- ubuntu 系统自带的 python 有多个版本,使用时难免会遇到环境变量出错,特别是当自动化运行脚本的时候。特别是近一个月来,实验室的小
- 除了在Matlab中使用PRTools工具箱中的svm算法,Python中一样可以使用支持向量机做分类。因为Python中的sklearn库
- 本文实例讲述了Python实现计算圆周率π的值到任意位的方法。分享给大家供大家参考,具体如下:一、需求分析输入想要计算到小数点后的位数,计算
- 最近在改一个页面,原来的编码是gb2312,为了国际化,改成utf-8,开始时浏览还是正常。因为电脑偶感小恙,于是恢复了系统,这才发现改后的
- 我准备在ASP中连接MYSQL了,请问如何做?首先要正确安装MYSQLX,装好之后,可调用以下程序即可正常访问MYSQL:<%@&nb
- SQL Server 客户端配置工具用于配置客户端的工具(除基于DOS操作系统的客户端工具以外),以便使它们可以成功地和SQL Server
- Python中的布尔类型Python中的布尔类型(bool)只有两个取值,分别是True和False。bool类型通常用于逻辑判断和条件控制
- 最近遇到一个问题,就是获取表单中的日期往后台通过json方式传的时候,遇到Date.parse(str)函数在ff下报错: NAN 找了些资
- 源码解读Bootstrap按钮按钮组按钮组和下拉菜单组件一样,需要依赖于bootstrap.js。使用“btn-group”的容器,把多个按
- 上线 Django 项目记录,超简单,避免无意义的踩坑!第一步:安装python管理器在宝塔在线面板安装“ python项目管理器 ”第二步
- SessionMiddleware 激活后,每个传给视图(view)函数的第一个参数``HttpRequest`` 对象都有一个 sessi
- 本文实例讲述了python实现中文分词FMM算法。分享给大家供大家参考。具体分析如下:FMM算法的最简单思想是使用贪心算法向前找n个,如果这
- 目录准备数据集导入所需的软件包将数据从文件加载到Python变量拆分数据进行训练和测试标记化并准备词汇预处理输出标签/类建立Keras模型并
- PHP chr() 函数实例从不同 ASCII 值返回字符:<?php echo chr(52) . "<br>
- 1.交换变量值2.将一列表中的所有元素拼接成字符串3.查找list中最高频率的值4.检查两个单词是否是字谜(组成的字母和对应数量一致)5.反
- 设计师在抱怨开发人员不尊重Web标准,后台开发人员在抱怨为什么不可以增加一个空格。PM在抱怨为什么项目总是因为那些看似简单的问题而延期……如
- b.php的代码 <?php //只能通过post方式访问 if ($_SERVER['REQUEST_METHOD'
- 您在访问网站时是否会在有些页面上见到这种功能---您在可以访问此网站的同时,还可以查看您免费邮箱中是否有新邮件。这个功能是不是让您觉得很心动