试卷征集
加入会员
操作视频

给定n个正整数,将它们分组,使得每组中的任意两个数互质(它们的最大公约数为1)。按照以下算法可以得到最少的组数:
第一步:将第1个整数分到第1组;
第二步:尝试将第2个至第n个整数分到已有的分组中,若能分到已有的分组中,则分到第一个符合条件的组;若不能分到已有的组,则分到新生成的组中。
例如对“70,99,25,54,11,100”6个整数分组,具体分组情况如下表所示a
组别 第1组
位置 0 1 2 3 4 5 6
2 70 99 0 0 0 0
组别 第2组
位置 7 8 9 10 11 12 13 ...
3 25 54 11 0 0 0 ...
程序运行时,输入n个整数,输出分组情况及至少分的组数,运行效果如下所示。
分组数据:70,99,25,54,11,100
分组情况:
第1组:70  99
第2组:25  54  11
第3组:100
至少分:3组
实现上述功能的程序如下,请回答下列问题:
n=6
global a,b#定义a,b为全局变量
def gcd(num1,num2):
#求整数num1、num2的公约数,代码略
def dist(x,m):#把整数x进行分组
dist=0
flag=False
For i in range(1,m+1):
flagp=True
    ②
for j in range(1,b[t]+1):
if gcd(x,b[t+j])>1:
flagp=False
break
if flagp==True:
b[t]+=1
b[t+b[t]]=x
flag=True
break
if flag==False:
t=m*(n+1)
b[t]+=1
     ③
dist=1
return dist
#输入n个整数,并存储在列表a中,代码略
b=[0]*(n*(n+1))#数组b分为n段,并将元素初始化为0
b[0]=1
b[1]=a[0]
cnt=1
s=””
For i in range(1,n):
cnt=    ①
#输出具体分组情况,代码略
print(“至少分:”,str(cnt),”组”)
(1)按照上述算法,若有“25,15,18,22,51,33,7,62”8个整数,至少分组数为
(2)请在横线处填入合适的代码。

【答案】(1)4
(2)①cnt+dist(a[i],cnt)
②t=(i-1)*(n+1)
③b[t+1]=x或b[b[t]+1]=x
【解答】
【点评】
声明:本试题解析著作权属菁优网所有,未经书面同意,不得复制发布。
发布:2024/6/27 10:35:59组卷:0引用:1难度:0.3
相似题
  • 1.有如下VB程序段:

    在文本框Text 1中输入“985-3+-”,执行该程序段后,文本框Text2中显示的值为(  )

    发布:2025/1/2 11:0:1组卷:1引用:1难度:0.4
  • 2.某 vb 工程的代码窗口如图所示,则下列说法正确的是(  )

    发布:2025/1/2 11:0:1组卷:0引用:1难度:0.4
  • 3.小李编写了按奇数位数字升序和偶数位数字降序排列的 VB 程序,功能如下:程序运行时,在标签 Label1 中显示排序前的数字,单击“排序”按钮,在标签 Label2 中输出排序的结果,运行界面如图所示。

    实现上述功能的 VB 程序如下。


    (1)根据程序代码,窗体中显示“排序”文字的按钮对象名称为_____。
    (2)程序代码中,加框处代码有错,请改正。
    (3)程序代码中,将 Label2.Caption 赋值语句补充完整。
    (4)程序代码中,与下划线语句 i Mod 2=0 功能相同的是_____ (单选,填字母:A.j Mod2=1/B.(i+j) Mod 2=0/C.k<>i)

    发布:2025/1/2 11:0:1组卷:0引用:1难度:0.9
深圳市菁优智慧教育股份有限公司
粤ICP备10006842号公网安备44030502001846号
©2010-2025 jyeoo.com 版权所有
APP开发者:深圳市菁优智慧教育股份有限公司| 应用名称:菁优网 | 应用版本:5.0.7 |隐私协议|第三方SDK|用户服务条款
广播电视节目制作经营许可证|出版物经营许可证|网站地图
本网部分资源来源于会员上传,除本网组织的资源外,版权归原作者所有,如有侵犯版权,请立刻和本网联系并提供证据,本网将在三个工作日内改正