论述题1. 题目描述:
求出用1,2,5这三个数不同个数组合的和为100的组合个数。为了更好地理解题目的意思,下面给出几组可能的组合:100个1,0个2和0个5,它们的和为100;50个1,25个2,0个5的和也是100;50个1,20个2,2个5的和也为100。
方法一:蛮力法
最简单的方法就是对所有的组合进行尝试,然后判断组合的结果是否满足和为100,这些组合有如下限制:1的个数最多为100个,2的个数最多为50个,5的个数最多为20个。实现思路为:遍历所有可能的组合1的个数x(0<=x<=100),2的个数y(0=<y<=50),5的个数z(0<=z<=20),判断x+2y+5z是否等于100,如果相等,则满足条件,实现代码如下:
package main
import(
"fmt"
)
func combinationCount(n int)int{
count:=0
num1:=n //1最多的个数
num2:=n/2 //2最多的个数
num5:=n/5 //5最多的个数
forx:=0; x<=num1; x++{
fory:=0; y<=num2; y++{
forz:=0; z<=num5; z++{
if(x+2*y+5*z==n){//满足条件
count++
}
}
}
}
return count
}
func main(){
fmt.Println(combinationCount(100))
}
程序的运行结果为
541
算法性能分析:
这种方法循环的次数为101*51*21。
方法二:数字规律法
针对这种数学公式的运算,一般都可以通过找出运算的规律进而简化运算的过程,对于本题而言,对x+2y+5z=100进行变换可以得到x+5z=100-2y。从这个表达式可以看出,x+5z是偶数且x+5z<=100。因此,求满足x+2y+5z=100组合的个数就可以转换为求满足“x+5z是偶数且x+5z<=100”的个数。可以通过对z的所有可能的取值(0<=z<=20)进行遍历从而计算满足条件的x的值。
当z=0时,x的取值为0,2,4,…,100(100以内所有的偶数),个数为(100+2)/2
当z=1时,x的取值为1,3,5,…,95(95以内所有的奇数),个数为(95+2)/2
当z=2时,x的取值为0,2,4,…,90(90以内所有的偶数),个数为(90+2)/2
当z=3时,x的取值为1,3,5,…,85(85以内所有的奇数),个数为(85+2)/2
当z=19时,x的取值为5,3,1(5以内所有的奇数),个数为(5+2)/2
当z=20时,x的取值为0(0以内所有的偶数),个数为(0+2)/2
根据这个思路,实现代码如下:
func combinationCount2(n int)int{
count:=0
form:=0; m<=n; m+=5 {
count+=(m+2)/2=
}
return count
}
算法性能分析:
这种方法循环的次数为21。
[考点] 如何组合1,2,5这三个数使其和为100
2. 题目描述:
100个灯泡排成一排,第一轮将所有灯泡打开;第二轮每隔一个灯泡关掉一个,即排在偶数的灯泡被关掉,第三轮每隔两个灯泡,将开着的灯泡关掉,关掉的灯泡打开。依次类推,第100轮结束的时候,还有几盏灯泡亮着?
对于每盏灯,当拉动的次数是奇数时,灯就是亮着的,当拉动的次数是偶数时,灯就是关着的。
(2)每盏灯拉动的次数与它的编号所含约数的个数有关,它的编号有几个约数,这盏灯就被拉动几次。
(3)1~100这100个数中有哪几个数,约数的个数是奇数?
我们知道,一个数的约数都是成对出现的,只有完全平方数约数的个数才。是奇数个。
所以,这100盏灯中有10盏灯是亮着的,它们的编号分别是:1、4、9、16、25、36、49、64、81、100。
下面是程序的实现:
package main
import(
"fmt"
)
func factorIsOdd(a int)int{
var totalint
fori:=1; i<=a; i++{
if a%i==0{total++)
}
if total%2==1{return1)else{return0}
}
func totalCount(num[]int, n int)int{
var coumint
fori:=0; i<n; i++{ //判断因子数是否为奇数,如果是奇数(灯亮)则加1
if factorIsOdd(num[i])==1{
fmt.Println("亮着的灯的编号是:", num[i])
count++
}
}
return count
}
func main(){
num:=make([]int, 100)
fori:=0; i<100; i++{num[i]=i+1}
count:=totalCount(num, 100)
fmt.Println("最后总共有", count, "盏灯亮着")
}
程序的运行结果为
亮着的灯的编号是:1
亮着的灯的编号是:4
亮着的灯的编号是:9
亮着的灯的编号是:16
亮着的灯的编号是:25
亮着的灯的编号是:36
亮着的灯的编号是:49
亮着的灯的编号是:64
亮着的灯的编号是:81
亮着的灯的编号是:100
最后总共有10盏灯亮着。
[考点] 如何判断还有几盏灯泡还亮着
3. 如何进行选择排序?
选择排序是一种简单直观的排序算法,它的基本原理如下:对于给定的一组记录,经过第一轮比较后得到最小记录,然后将该记录与第一个记录的位置进行交换;接着对不包括第一个记录以外的其他记录进行第二轮比较,得到最小记录并与第二个记录进行位置交换;重复该过程,直到进行比较的记录只有一个时为止。以数组{38,65,97,76,13,27,49}为例,具体步骤如下:
第一趟排序后:13 [65 97 76 38 27 49]
第二趟排序后:13 27 [97 76 38 65 49]
第三趟排序后:13 27 38 [76 97 65 49]
第四趟排序后:13 27 38 49 [97 65 76]
第五趟排序后:13 27 38 49 65 [97 76]
第六趟排序后:13 27 38 49 65 76 [97]
最后排序结果:13 27 38 49 65 76 97
程序示例如下:
package main
import(
"fmt"
)
func SelectSort(data[]int){
llen:=len(data)
fori:=0; i<llen; i++{
tmp:=data[i]
flag:=i
forj:=i+1; j<llen; j++{
if data[j]<tmp{
tmp=data[j]
flag=j
}
}
if flag!=i{
data[flag]=data[i]
data[i]=tmp
}
}
}
func main(){
data:=[]int{5, 4, 9, 8, 7, 6, 0, 1, 3, 2}
SelectSort(data)
fmt.Println(data)
}
程序运行结果为:
0 1 2 3 4 5 6 7 8 9
[考点] 如何进行选择排序
4. 题目描述:
如何进行插入排序?
对于给定的一组记录,初始时假设第一个记录自成一个有序序列,其余的记录为无序序列。接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至最后一个记录插入到有序序列中为止。以数组{38,65,97,76,13,27,49}为例,直接插入排序具体步骤如下:
第一步插入38以后:[38] 65 97 76 13 27 49
第二步插入65以后:[38 65] 97 76 13 27 49
第三步插入97以后:[38 65 97] 76 13 27 49
第四步插入76以后:[38 65 76 97] 13 27 49
第五步插入13以后:[13 38 65 76 97] 27 49
第六步插入27以后:[13 27 38 65 76 97] 49
第七步插入49以后:[13 27 38 49 65 76 97]
程序示例如下:
package main
import(
"fmt"
)
func InsertSort(array[]int){
if array==nil{return}
fori:=1; i<len(array); i++{
trap, j:=array[i], i
if array[j-1]>tmp{
for j>=1&&array[j-1]>tmp{
array[j]=array[j-1]
j--
}
}
array[j]=tmp
}
}
func main(){
array:=[]int{7, 3, 19, 40, 4, 7, 1};
InsenSort(array);
fmt.Println(array)
}
程序运行结果为:
1 3 4 7 7 19 40
[考点] 如何进行插入排序
5. 题目描述:
如进行冒泡排序?
冒泡排序顾名思义就是整个过程就像气泡一样往上升,单向冒泡排序的基本思想是(假设由小到大排序):对于给定的n个记录,从第一个记录开始依次对相邻的两个记录进行比较,当前面的记录大于后面的记录时,交换其位置,进行一轮比较和换位后,n个记录中的最大记录将位于第n位;然后对前(n-1)个记录进行第二轮比较;重复该过程直到进行比较的记录只剩下一个时为止。
以数组{36,25,48,12,25,65,43,57}为例,具体排序过程如下:
一趟排序的过程如下:
R[1] 36 25 25 25 25 25 25 25
R[2] 25 36 36 36 36 36 36 36
R[3] 48 48 48 12 12 12 12 12
R[4] 12 12 12 48 25 25 25 25
R[5] 25 25 25 25 48 48 48 48
R[6] 65 65 65 65 65 65 43 43
R[7] 43 43 43 43 43 43 65 57
R[8] 57 57 57 57 57 57 57 65
则经过多趟排序后的结果如下:
初始状态:[36 25 48 12 25 65 43 57]
1趟排序:[25 36 12 25 48 43 57 65]
2趟排序:[25 12 25 36 43 48] 57 65
3趟排序:[12 25 25 36 43] 48 57 65
4趟排序:[12 25 25 36] 43 48 57 65
5趟排序:[12 25 25] 36 43 48 57 65
6趟排序:[12 25] 25 36 43 48 57 65
7趟排序:[12] 25 25 36 43 48 57 65
程序示例如下:
package main
import(
"fmt"
)
func BubbleSort(array[]jnt){
llen:=len(array)
fori:=0; i<llen-1; i++{
forj:=llen-1; j>i; j--{
if array[j]<array[j-1]{
tmp:=array[j]
array[j]=array[j-1]
array[j-1]=tmp
}
}
}
}
func main(){
array:=[]int{5, 4, 9, 8, 7, 6, 0, 1, 3, 2}
BubbleSort(array)
fmt.Println(array)
}
程序输出为
0 1 2 3 4 5 6 7 8 9
[考点] 如进行冒泡排序