例如,求72和40的最大公因数,即计算GCD(724,344):
GCD(724,344)=GCD(344,724%344)=GCD(344,36)
=GCD(36,344%36)=GCD(36,20)
=GCD(20,36%20)=GCD(20,16)
=GCD(16,20%16)=GCD(16,4)
=GCD(4,16%4)=GCD(4,0)
=4
问题描述:给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下:
(1)n∈set(n);
(2)在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半:
(3)按此规则进行处理,直到不能再添加自然数为止.
例如,set(6)={6,16,26,126,36,136}.半数集set(6)中有6个元素.注意,该半数集不是多重集.集合中已经有的元素不再添加到集合中.
算法设计:对于给定的自然数n,计算半数集set(n)中的元素个数.
数据输入:输入数据由文件名为input.txt的文本文件提供.每个文件只有一行,给出整数n(0<n<1000).
结果输出:将计算结果输出到文件output.txt.输出文件只有一行,给出半数集set(n)中的元素个数.
根结点的数据,LT和RT是括号形式的左子树和右子树。要求空树不打印任何信息,一个结点的树的打印形式是x,而不应是(x,)的形式。
算法设计:设计一个拉斯维加斯算法,对于给定的自然数n(1≤n≤100)计算在n×n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格,且放置的皇后互不攻击.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n.
结果输出:将计算的最少皇后数及最佳放置方案输出到文件output.txt.文件的第1行是最少皇后数:接下来的1行是皇后的最佳放置方案.
试编写算法,计算的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,...,n)。假设计算机中允许的整数最大值为maxint,则当n>arrsize或对某个
,使
时, 应按出错处理。注意选择你认为较好的出错处理方法。
问题描述:假设有来自n个不同单位的代表参加一次国际会议.铄个单位的代表数分别为ri(i=1,2,...,n).会议餐厅共有m张餐桌,每张餐桌可容纳ci(i=1,2,...,m)个代表就餐.为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐.试设计一个算法,给出满足要求的代表就餐方案.
算法设计:对于给定的代表数和餐桌数以及餐桌容量,计算满足要求的代表就餐方案.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数m和n,m表示餐桌数,n表示单位数(1≤m≤150,1≤n≤270).文件第2行有m个正整数,分别表示每个单位的代表数.文件第3行有n个正整数,分别表示每个餐桌的容量.
结果输出:将代表就餐方案输出到文件output.txt如果问题有解,在文件第1行输出1,否则输出0.接下来的m行给出每个单位代表的就餐桌号.如果有多个满足要求的方案,只要输出一个方案.