基础练习

1.十六进制转八进制

问题描述
　　给定n个十六进制正整数，输出它们对应的八进制数。

输入格式
　　输入的第一行为一个正整数n （1<=n<=10）。
　　接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。

输出格式
　　输出n行，每行为输入对应的八进制正整数。

　　【注意】
　　输入的十六进制数不会有前导0，比如012A。
　　输出的八进制数也不能有前导0。

样例输入
　　2
　　39
　　123ABC

样例输出
　　71
　　4435274

源代码

  1. n=int(input())
  2. if (n>=1)&(n<=10):
  3.     alist=n*[0]
  4.     i=0
  5.     while i<n:
  6.         alist[i]=input()
  7.         i+=1
  8.     for i in range(0,len(alist)):
  9.         alist[i]=int(alist[i],16)
  10.         alist[i]=str(oct(alist[i]))[2:]  #将八进制默认输出的0o去掉 
  11.         print(alist[i])
  12. """
  13. int('A',16)    # 字符串转换成16进制整数
  14. hex(16)     # 10进制转16进制
  15. oct(8)      # 10进制转8进制
  16. bin(8)      # 10进制转2进制
  17. """

2.特殊回文数

问题描述
　　123321是一个非常特殊的数，它从左边读和从右边读是一样的。
　　输入一个正整数n， 编程求所有这样的五位和六位十进制数，满足各位数字之和等于n 。
输入格式
　　输入一行，包含一个正整数n。
输出格式
　　按从小到大的顺序输出满足条件的整数，每个整数占一行。
样例输入
52
样例输出
899998
989989
998899
数据规模和约定
　　1<=n<=54。

源代码：

运行超时：

  1. def huiwen(n):  
  2.     ans=0
  3.     nn=n
  4.     while nn>0:
  5.         ans=ans*10 + (nn%10)
  6.         nn=int(nn/10)
  7.     if ans==n:
  8.         return 1
  10.     return 0
  12. def add(n):
  13.     ans=0
  14.     while n>0:
  15.         ans+=n%10
  16.         n=int(n/10)
  17.     return ans
  19. n=int(input())
  20. for i in range(10000,1000000):    #遍历次数过多容易导致超时
  21.     if huiwen(i):
  22.         if add(i)==n:
  23.             print(i)

高效算法：

  1. n=int(input())
  2. def huiwen(n):
  3.     if n>45 and n%2==1:   #如果给的数是大于45的奇数就不存在五位或六位的回文数，因为5位回文数n<=45,
  4.         return            #六位回文数n一定是偶数
  6.     for i in range(1,10):                          
  7.         for j in range(0,10):
  8.             for k in range(0,10):
  9.                 if (2*(i+j)+k==n):
  10.                     sum=i*10001+j*1010+k*100
  11.                     print(sum)
  13.     if n%2==1:          #当n是奇数，没必要遍历六位回文数
  14.         return                
  15.     for i in range(1,10):
  16.         for j in range(0,10):
  17.             for k in range(0,10):
  18.                 if (2*(i+j+k)==n):
  19.                     sum=i*100001+j*10010+k*1100
  20.                     print(sum)
  21. huiwen(n)

3.回文数

问题描述
　　1221是一个非常特殊的数，它从左边读和从右边读是一样的，编程求所有这样的四位十进制数。
输出格式
　　按从小到大的顺序输出满足条件的四位十进制数。

源代码

  1. for i in range(1,10):
  2.     for j in range(0,10):
  3.         sum=i*1001+j*110
  4.         print(sum)

4.特殊的数字

问题描述
　　153是一个非常特殊的数，它等于它的每位数字的立方和，即153=111+555+333。编程求所有满足这种条件的三位十进制数。
输出格式
　　按从小到大的顺序输出满足条件的三位十进制数，每个数占一行。

源代码

  1. for i in range(1,10):
  2.     for j in range(0,10):
  3.         for k in range(0,10):
  4.             sum=i*100+j*10+k*1
  5.             if sum==pow(i,3)+pow(j,3)+pow(k,3):
  6.                 print(sum)

5.杨辉三角形

问题描述
杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)的展开式的系数。
它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。
下面给出了杨辉三角形的前4行：
1
1 1
1 2 1
1 3 3 1
给出n，输出它的前n行。
输入格式
输入包含一个数n。
输出格式
输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。
样例输入
4
样例输出
1
1 1
1 2 1
1 3 3 1
数据规模与约定
1 <= n <= 34。

源代码

利用二维数组，

  1. alist=[['1'],['1','1']]
  2. n=int(input())
  3. def yanghui(n):
  4.     for i in range(2,n):
  5.         s=(i+1)*[0]
  6.         s[0]='1'
  7.         s[i]='1'
  8.         for j in range(1,i):
  9.             s[j]=str(int(alist[i-1][j-1])+int(alist[i-1][j]))
  10.         alist.append(s)
  11.     for i in range(0,len(alist)):
  12.         print(' '.join(alist[i]))   #join要可以将字符列表转换为不带括号的元素
  13. yanghui(n)

6.查找整数

问题描述
给出一个包含n个整数的数列，问整数a在数列中的第一次出现是第几个。
输入格式
第一行包含一个整数n。
第二行包含n个非负整数，为给定的数列，数列中的每个数都不大于10000。
第三行包含一个整数a，为待查找的数。
输出格式
如果a在数列中出现了，输出它第一次出现的位置(位置从1开始编号)，否则输出-1。
样例输入
6
1 9 4 8 3 9
9
样例输出
2
数据规模与约定
1 <= n <= 1000。

源代码

  1. n=int(input())
  2. s=input().split()  #输入多个数，并用空格隔开
  3. k=input()
  4. for i in range(0,n):
  5.     if s[i]==k:
  6.         flag=i+1
  7.         break
  8.     else:
  9.         flag=-1
  10. print(flag)

7.数列特征

问题描述
给出n个数，找出这n个数的最大值，最小值，和。
输入格式
第一行为整数n，表示数的个数。
第二行有n个数，为给定的n个数，每个数的绝对值都小于10000。
输出格式
输出三行，每行一个整数。第一行表示这些数中的最大值，第二行表示这些数中的最小值，第三行表示这些数的和。
样例输入
5
1 3 -2 4 5
样例输出
5
-2
11
数据规模与约定
1 <= n <= 10000。

源代码

  1. n=int(input())
  2. s=input().split()
  3. for i in range(0,n):
  4.     s[i]=int(s[i])
  5. max=s[0]
  6. min=s[0]
  7. sum=s[0]
  8. for i in range(1,n):
  9.    if max<s[i]:
  10.        max=s[i]
  11.    if min>s[i]:
  12.        min=s[i]
  13.    sum+=(s[i])
  14. print(max)
  15. print(min)
  16. print(sum)

普及题

1.用筛法求之N内的素数

题目描述
用筛法求之N内的素数。
输入
N
输出
0～N的素数
样例输入
100
样例输出
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

源代码

  1. #定义一个列表prime,赋初值为0，列表索引表示对应的数字，通过数组值判断是否为素数
  2. #若prime[i]=0,则prime[i*j]=1,即i*j不是素数
  3. def Selbergsieve(n):
  4.     prime=(n*n)*[0]
  5.     for i in range(2,n):
  6.         if prime[i]==0:
  7.             j=2
  8.             while i*j<=n:
  9.                 prime[i*j]=1
  10.                 j+=1
  11.     for i in range(2,n):
  12.         if prime[i]==0:
  13.             print(i)
  16. n=int(input())
  17. Selbergsieve(n)
  19. ###优化的代码,省去了遍历数组的时间
  20. def Selbergsieve(n):
  21.     prime=(n*n)*[0]
  22.     for i in range(2,n):
  23.         if prime[i]==0:
  24.             j=2
  25.             print(i)
  26.             while i*j<=n:
  27.                 prime[i*j]=1
  28.                 j+=1
  30. n=int(input())
  31. Selbergsieve(n)

2.字符串的输入输出处理

字符串的输入输出处理。
输入
第一行是一个正整数N，最大为100。之后是多行字符串（行数大于N）， 每一行字符串可能含有空格，字符数不超过1000。
输出
先将输入中的前N行字符串（可能含有空格）原样输出，再将余下的字符串（不含有空格）以空格或回车分割依次按行输出。每行输出之间输出一个空行。
样例输入
2
www.dotcpp.com DOTCPP
A C M
D O T CPP
样例输出
www.dotcpp.com DOTCPP

A C M

D

O

T

CPP

源代码：

  1. n = int(input())
  2. for i in range(n):
  3.     print(input() + '\n')
  4. while True:
  5.     try:
  6.         slist = input().split()
  7.         for s in slist:
  8.             print(s + '\n')
  9.     except:
  10.         break

3.蛇形矩阵

蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。
输入
本题有多组数据，每组数据由一个正整数N组成。（N不大于100）
输出
对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。
样例输入
5
样例输出
1 3 6 10 15
2 5 9 14
4 8 13
7 12
11

源代码

image.png

  1. n = int(input())
  2. num=1
  3. x=2
  4. y=1
  5. while n:
  6.     num1=num
  7.     x1=x
  8.     for i in range(0,n):
  9.         print(num,end=' ') #不是换行输出，以空格隔开输出
  10.         num+=x
  11.         x+=1
  13.     print('\n')
  14.     num=num1+y
  15.     y+=1
  16.     x=x1+1
  17.     n-=1

4.ip判断

输入
输入由多行组成，每行是一个字符串，输入由“End of file”结束。
字符串长度最大为30，且不含空格和不可见字符
输出
对于每一个输入，单独输出一行
如果该字符串是合法的IP，输出Y，否则，输出N
样例输入
1.2.3.4
a.b.c.d
267.43.64.12
12.34.56.bb
210.43.64.129
-123.4.5.6
样例输出
Y
N
N
N
Y
N

源代码

  1. legalset=list(map(str,range(256)))
  2. try:
  3.     while True:
  4.         l=input().split('.')
  5.         s=True
  6.         for i in l:
  7.             if i not in legalset:
  8.                 print('N')
  9.                 s=False
  10.                 break
  11.         if s:
  12.             print('Y')
  13. except EOFError:
  14.     pass

5.Tom数

正整数的各位数字之和被Tom称为Tom数。求输入数（<2^32）的Tom数!
输入
每行一个整数(<2^32).
输出
每行一个输出,对应该数的各位数之和.
样例输入
12345
56123
82
样例输出
15
17
10

源代码

  1. while True:
  2.     try:
  3.         s=input()
  4.         i=0
  5.         s=list(s)
  6.         tom=0
  7.         while i<len(s):
  8.             tom+=int(s[i])
  9.             i+=1
  10.         print(tom)
  11.     except:
  12.         pass

6.分糖果

题目描述
问题描述
有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：

每个小朋友都把自己的糖果分一半给左手边的孩子。

一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。

反复进行这个游戏，直到所有小朋友的糖果数都相同为止。

你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。
输入
程序首先读入一个整数N(2< N< 100)，表示小朋友的人数。
接着是一行用空格分开的N个偶数（每个偶数不大于1000，不小于2）
输出
要求程序输出一个整数，表示老师需要补发的糖果数。
样例输入
3
2 2 4
样例输出
4

源代码

  1. n=int(input())
  2. s=input().split(' ')
  3. a=n*[0]
  4. num=0
  5. for i in range(0,n):
  6.     a[i]=int(s[i])
  7. while 1:
  8.     flag=True
  9.     for i in range(1,n):
  10.         if a[0]!=a[i]:
  11.             flag=False
  12.     if flag:
  13.         break
  14.     for i in range(0,n):
  15.         a[i]=int(a[i]/2)
  16.     temp=a[n-1]
  17.     j=n-1
  18.     while j>0:
  19.         a[j]+=a[j-1]
  20.         j-=1
  21.     a[0]+=temp
  22.     for i in range(0,n):
  23.         if a[i]%2!=0:
  24.             a[i]+=1
  25.             num+=1
  26. print(num)

7.数字游戏

栋栋正在和同学们玩一个数字游戏。

游戏的规则是这样的：栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数字1。接下来，坐在栋栋左手边的同学要说下一个数字2。再下面的一个同学要从上一个同学说的数字往下数两个数说出来，也就是说4。下一个同学要往下数三个数，说7。依次类推。

为了使数字不至于太大，栋栋和同学们约定，当在心中数到 k-1 时，下一个数字从0开始数。例如，当k=13时，栋栋和同学们报出的前几个数依次为：
1, 2, 4, 7, 11, 3, 9, 3, 11, 7。

游戏进行了一会儿，栋栋想知道，到目前为止，他所有说出的数字的总和是多少。

样例说明
栋栋说出的数依次为1, 7, 9，和为17。
数据规模和约定
1 < n,k,T < 1,000,000；

输入
输入的第一行包含三个整数 n,k,T，其中 n 和 k 的意义如上面所述，T 表示到目前为止栋栋一共说出的数字个数。
输出
输出一行，包含一个整数，表示栋栋说出所有数的和。
样例输入
3 13 3
样例输出
17

image.png

源代码

  1. n,k,T=map(int,input().split())
  2. num=1
  3. a=1
  4. j=1
  5. dd=0
  6. i=1
  7. while num<=T:
  8.     dd+=a
  9.     wm=(n*i+int(n*(n-1)/2)+a)%k  
  10.     a=wm
  11.     num+=1
  12.     i+=n
  13. print(dd)
  16. ###超时
  17. n,k,T=map(int,input().split())
  18. num=0
  19. a=n*[1]
  20. j=1
  21. dd=0
  22. while num<T:
  23.     dd+=a[0]
  24.     num+=1
  25.     for i in range(1,n):
  26.         wd,wm=divmod(a[i-1]+j,k)
  27.         a[i]=a[i-1]+j
  28.         j+=1
  29.     wdd,wmm=divmod(a[n-1]+j,k)
  30.     if wdd>0:
  31.         a[0]=wmm
  32.     else:
  33.         a[0]=a[n-1]+j
  35.     j+=1
  37. print(dd)

8.核桃的数量(求三个数的最小公倍数)

小张是软件项目经理，他带领3个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：
1. 各组的核桃数量必须相同
2. 各组内必须能平分核桃（当然是不能打碎的）
3. 尽量提供满足1,2条件的最小数量（节约闹革命嘛）

输入
输入包含三个正整数a, b, c，表示每个组正在加班的人数，用空格分开（a,b,c< 30）
输出
输出一个正整数，表示每袋核桃的数量。
样例输入
2 4 5
样例输出
20

源代码

  1. a,b,c=map(int,input().split())
  2. al=[a,b,c]
  3. al.sort()
  4. maxnum=al[2]
  5. while 1:
  6.     if (maxnum%al[0]==0 and maxnum%al[1]==0 and maxnum%al[2]==0):
  7.         break
  8.     maxnum+=1
  10. print(maxnum)

提高题

1.2^k进制数

设r是个2^k 进制数，并满足以下条件：
（1）r至少是个2位的2^k 进制数。
（2）作为2^k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。
（3）将r转换为2进制数q后，则q的总位数不超过w。
在这里，正整数k（1≤k≤9）和w（k〈w≤30000）是事先给定的。

问：满足上述条件的不同的r共有多少个？
我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2^k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2^k 进制数r。
例：设k=3，w=7。则r是个八进制数（2^3=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：
2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。
3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。
所以，满足要求的r共有36个。
输入
只有1行，为两个正整数，用一个空格隔开：
k w
输出
1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。
（提示：作为结果的正整数可能很大，但不会超过200位）
样例输入
3 7
样例输出
36

源代码

  1. k,w=map(int,input().split())
  2. wd,wm=divmod(w,k) #wd是商，wm是余数
  3. def c(m,n):    #当m=7,n=3,求7*6*5/(3*2*1)
  4.     if n>m:
  5.         return 0
  6.     if n<0:
  7.         return 0
  8.     s=1
  9.     for i in range(n):
  10.         s=s*(m-i)//(i+1)
  11.     return s
  12. #s0求的是首位为0的情况
  13. s0=sum([c(2**k-1,i) for i in range(2,wd+1)])  #sum([x,y,z...])求x+y+z+...的和
  14. s1=sum([c(2**k-1-x0,wd) for x0 in range(1,2**wm)])  #2**k表示2^k
  15. print(s0+s1)

2.Huffuman树

**Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。

给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：

  1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。

  2. 重复步骤1，直到{pi}中只剩下一个数。

在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。

本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：

  1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。

  2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。

  3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。

  4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。

  5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
    输入
    输入的第一行包含一个正整数n（n< =100）。

接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出
输出用这些数构造Huffman树的总费用。

源代码

  1. ###答案错误9%
  2. n=int(input())
  3. s=input().split()
  4. p=n*[0]
  5. for i in range(0,n):
  6.     p[i]=int(s[i])
  7. num=0
  9. while len(p)>1:
  10.     p.sort(reverse=True)
  11.     a1=p.pop()
  12.     a2=p.pop()
  13.     p.append(a1+a2)
  14.     p.sort(reverse=True)
  15.     print(p)
  16.     num+=(a1+a2)
  18. print(num)

3.K-进制数

考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.

例:
1010230 是有效的7位数
1000198 无效
0001235 不是7位数, 而是4位数.

给定两个数N和K, 要求计算包含N位数字的有效K-进制数的总数.

假设2 <= K <= 10; 2 <= N; 4 <= N+K <= 18.
输入
两个十进制整数N和K
输出
十进制表示的结果
样例输入
2
10
样例输出
90

源代码

为满足提议，最多可以有n/2个0：101010101010…
将插入的0的个数为0，1，2……n/2且满足题意的数的个数相加，就是最终结果，因为插入n/2+1个0的时候就不能满足题意

  1. n=int(input())
  2. k=int(input())
  3. num=0
  4. def c(m,n,k,N):    #当m=7,n=3,求7*6*5/(3*2*1)*pow(k-1,N-n)
  5.     if n>m:
  6.         return 0
  7.     if n<0:
  8.         return 0
  9.     s=1
  10.     for i in range(n):
  11.         s=s*(m-i)//(i+1)
  12.     s=s*pow(k-1,N-n)
  13.     return s
  15. s=sum([c(n-i,i,k,n) for i in range(0,round(n/2)+1)])
  16. print(s)

4.能量项链

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有 N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标 记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗 能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为mrn（Mars单位），新产生的珠子的头标记为m， 尾标记为n。
需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号◎表示两颗珠子的聚合操作，(j◎k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4◎1)=1023=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4◎1)◎2)◎3）=1023+1035+10510=710。
输入
第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行 是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i〈N时，第i颗珠子的尾标记应该等于第i+1颗 珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
输出
只有一行，是一个正整数E（E≤2.1*10^9），为一个最优聚合顺序所释放的总能量
样例输入
4
2 3 5 10
样例输出
710

源代码

  1. """
  2.   1.从N个球里选择标记和最小的，然后与前一个球聚合形成一个新的球
  3.   2.从N-1个球中选择标记和最小的球，重复第一步操作
  4.   3.直到没有球为止
  5. """
  6. N = int(input())
  7. num = list(map(int,input().split()))
  8. arr = [([0]*2) for i in range(N)]
  9. for i in range(N):
  10.     if i+1 == N:
  11.         arr[i] = num[i],num[0]
  12.     else:
  13.         arr[i] = num[i],num[i+1]
  14. def minest(arr,N):
  15.     #print(min(arr))
  16.     return arr.index(min(arr))
  17. ans = 0
  18. for i in range(N-1):
  19.     start = minest(arr,N)-1   #arr[-1]=arr[N-1]
  20.     #print(arr[start])
  21.     ans += arr[start][0]*arr[start+1][0]*arr[start+1][1]
  22.     arr[start+1] = arr[start][0],arr[start+1][1]
  23.     del arr[start]
  24.     #print(arr)
  25. print(ans)

5.插入排序

**排序，顾名思义，是将若干个元素按其大小关系排出一个顺序。形式化描述如下：有n个元素a[1]，a[2]，…，a[n]，从小到大排序就是将它们排成一个新顺序a[i[1]]< a[i[2]]< …< a[i[n]]
i[k]为这个新顺序。
插入排序，顾名思义，是通过插入操作完成排序。其直觉和方法来源于打牌时安排牌的方法。每次摸起一张牌，你都会将其插入到现在手牌中它按顺序应在的那个位置。插入排序每一步都类似这个摸牌过程。比如现在有整数数组：{3, 1, 5, 4, 2}
第一步：插入3 得到新序列{3}
第二步：插入1 得到新序列{1 3}
第三步：插入5 得到新序列{1 3 5}
第四步：插入4 得到新序列{1 3 4 5}
第五步：插入2 得到新序列{1 2 3 4 5}
为了看程序中如何完成插入过程，我们以第五步为例：
初始时：1 3 4 5 2
将2存入临时变量tmp
将下标j指向2之前的元素5，然后根据tmp和a[j]的大小关系决定该元素是否应该后移。如果a[j]> tmp，则将a[j]后移到a[j+1]，序列变成1 3 4 5 5。
将下标j前移
判断a[j]> tmp，后移a[j]到a[j+1]，得到1 3 4 4 5
将下标j前移
判断a[j]> tmp，后移a[j]到a[j+1]，得到1 3 3 4 5
因为a[j]< =tmp，所以将tmp放回a[j+1]，得到 1 2 3 4 5
现在，输入n个整数，根据以上算法，输出插入排序的全过程。

数据规模和约定
n< =100
整数元素在int范围内
输入
第一行一个正整数n，表示元素个数
第二行为n个整数，以空格隔开
输出
　有n个元素，因此输出部分分为n个部分，每个部分开头行为：Insert element[i]，i为第几个元素。然后对于每一个部分，输出该部分该元素在插入排序过程中的每一步产生的新序列，初始时的序列以Init:打头，然 后每一步后移数组元素后的元素序列以Move back:打头，最后得到的最终结果序列以Final:打头。序列元素间以一个空格隔开。示例请看样例输出。每一个部分的Insert element[i]之后的每一步的输出行之前要缩进两格，即输出两个空格。
样例输入
5
3 1 5 4 2
样例输出
Insert element[1]:
Init:3
Final:3
Insert element[2]:
Init:3 1
Move back:3 3
Final:1 3
Insert element[3]:
Init:1 3 5
Final:1 3 5
Insert element[4]:
Init:1 3 5 4
Move back:1 3 5 5
Final:1 3 4 5
Insert element[5]:
Init:1 3 4 5 2
Move back:1 3 4 5 5
Move back:1 3 4 4 5
Move back:1 3 3 4 5
Final:1 2 3 4 5

源代码