其中1-30题采用Python2.7,31-36题采用Python3.7

(1)有1、2、3、4四个数字,能组成哪些互不相同且无重复数字的三位数?

# -*- coding: utf-8 -*-
for i in range(1,5):
    for j in range(1,5):
        for k in range(1,5):
            num = i*100+j*10+k;
            if(i!=j & j!=k):
                print num

 

(2)企业发放的奖金根据利润提成。利润(i)低于或等于10万元时,奖金可提10%;利润高于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可提成7.5%;20万到40万之间时,高于20万元的部分,可提成5%;40万到60万之间时高于40万元的部分,可提成3%;60万到100万之间时,高于60万元的部分,可提成1.5%,高于100万元时,超过100万元的部分按1%提成,求当利润为i时应发放奖金总数。

# -*- coding: utf-8 -*-
num = input()
sum = 0
if(num <= 100000):
    sum = sum + num * 0.1
if(num > 100000 & num <= 200000):
    sum = sum + 100000 * 0.1 + (num-100000) * 0.075
if(num > 200000 & num <= 400000):
    sum = sum + 100000 * 0.1 + 100000 * 0.075 + (num - 200000) * 0.05
if(num >400000 & num <= 600000):
    sum = sum + 100000 * 0.1 + 100000 * 0.075 + 200000 * 0.05 + (num - 400000) * 0.03
if(num > 600000 & num <=1000000):
    sum = sum + 100000 * 0.1 + 100000 * 0.075 + 200000 * 0.05 + 200000 * 0.03 + (num - 600000) * 0.015
if(num > 1000000):
    sum = sum + 100000 * 0.1 + 100000 * 0.075 + 200000 * 0.05 + 200000 * 0.03 + 400000 * 0.015 + (num - 1000000) * 0.01
print sum

 

(3)输入某年某月某日,判断这一天是这一年的第几天?

# -*- coding: utf-8 -*-
 
def leapyear(year):
    return ((year % 400 == 0) | (year % 4 == 0 & year % 100 != 0))
 
sum = 0
year = input("请输入年:")
month = input("请输入月:")
day = input("请输入日:")
if(month > 1):
    sum = sum + 31
if(month > 2):
    if(leapyear(year)):
        sum = sum + 29
    else:
        sum = sum + 28
if(month > 3):
    sum = sum + 31
if(month > 4):
    sum = sum + 30
if(month > 5):
    sum = sum + 31
if(month > 6):
    sum = sum + 30
if(month > 7):
    sum = sum + 31
if(month > 8):
    sum = sum + 31
if(month > 9):
    sum = sum + 30
if(month > 10):
    sum = sum + 31
if(month > 11):
    sum = sum + 30
 
sum = sum + day
print ("第%d天" %(sum))

 

(4)使用□■输出国际象棋棋盘(8*8)。

# -*- coding: utf-8 -*-
 
for i in range(1,9):
    for j in range(1,9):
        if((i+j)%2 == 0):
            print("□"),
        else:
            print("■"),
    print("")

 

(5)有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第N个月的兔子总数为多少?

# -*- coding: utf-8 -*-
num = input()
a = 1
b = 1
 
def fun(num):
    if(num == 1):
        return 1
    elif(num == 2):
        return 1
    else:
        return fun(num - 1) + fun(num - 2)
print 2*fun(num)

 

(6)将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。

# -*- coding: utf-8 -*-
num = input()
print(num),
print("="),
for i in range(2,num):
    if(num == 1):
        break;
    while(num % i == 0):
        print(i),
        num = num / i;
        if(num != 1):
            print("*"),

 

(7)输入一个字符串,分别统计出其中英文字母、空格、数字和其它字符的个数。

# -*- coding: utf-8 -*-
str = raw_input()
alpha = 0
space = 0
number = 0
other = 0
for i in str:
    if(i.isalpha()):
        alpha=alpha + 1
    elif(i.isdigit()):
        number = number + 1
    elif(i.isspace()):
        space = space + 1
    else:
        other = other + 1
print("英文字母数=%d"%alpha)
print("数字数=%d"%number)
print("空格数=%d"%space)
print("其他字符数=%d"%other)

 

(8)输入a,n(0<a<10, 0<n<10),求s=a+aa+aaa+aaaa+aa…a(n个a)的值。例如a=2,n=5时为:2+22+222+2222+22222。

# -*- coding: utf-8 -*-
a = input()
n = input()
 
sum = 0
for i in range(n,0,-1):
    sum = sum + i * a
    a = a * 10
print sum

 

(9) 一球从100米高度自由落下,每次落地后反跳回原高度的一半;再落下,求它在第10次落地时,共经过多少米?第10次反弹多高?

# -*- coding: utf-8 -*-
num = 100.0
sum = 100.0
for i in range(0,9):
    num = num / 2.0
    sum = sum + num * 2.0
print ("第十次:%f"%(num/2.0))
print ("总距离:%f"%sum)

 

(10) 猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时,见只剩下一个桃子了。求第一天共摘了多少?

# -*- coding: utf-8 -*-
num= 1
for i in range(0,9):
    num= (num + 1)*2
print num

 

(11) 两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比,c说他不和x,z比,请编程序找出三队赛手的名单。

# -*- coding: utf-8 -*-
def fun(num):
    if num == 0:
        return "X"
    if num == 1:
        return "Y"
    if num == 2:
        return "Z"
 
for i in range(0,3):
    for j in range(0,3):
        if(i != j):
            for k in range(0,3):
                if(i != k and j != k):
                    if(k != 0 and i != 0 and k != 2):
                        print "A vs",
                        print fun(i)
                        print "B vs",
                        print fun(j)
                        print "C vs",
                        print fun(k)

 

(12) 求1+2!+3!+…+20!的和。

# -*- coding: utf-8 -*-
def fun(num):
    if(num == 1):
        return 1
    else:
        return num * fun(num-1)
 
sum = 0
for i in range(1,21):
    sum = sum + fun(i)
 
print sum

 

(13) 给一个不多于5位的正整数,要求:一、求它是几位数,二、逆序打印出各位数字。

# -*- coding: utf-8 -*-
 
def printConverse(num):
    count = 0
    while(num != 0):
        temp = num % 10
        print temp,
        num = num/10
        count = count + 1
    return count
 
num = input()
print num,
print "逆序输出:",
a = printConverse(num)
print "位数为:",
print a

 

(14)有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13…求出这个数列的前20项之和,用分数形式表现出来。

(1)使用fractions库函数实现

# -*- coding: utf-8 -*-
import fractions
from fractions import  Fraction
a = 2
b = 1
sum = 0
for i in range(0,20):
    sum = sum + Fraction(a,b)
    temp = a
    a = a + b
    b = temp
 
print sum

(2)不用fractions库函数实现

# -*- coding: utf-8 -*-
a = 1
b = 2
denominator = 1
denominator = denominator * a * b
arrayDen = [1,2]
arrayNum = [2]
for i in range(0,18):
    sum = a + b
    arrayDen.append(sum)
    a = b
    b = sum
    denominator = denominator * sum
    arrayNum.append(sum)
 
arrayNum.append(a+b)
 
sumDen = denominator
sumNum = 0
for i in range(0,20):
    sumNum = sumNum + sumDen/arrayDen[i]*arrayNum[i]
 
for i in range(0,20):
    if(sumDen % arrayDen[i] == 0 and sumNum % arrayDen[i] == 0):
        sumDen = sumDen / arrayDen[i]
        sumNum = sumNum / arrayDen[i]
    if(sumDen % (i+1) == 0 and sumNum % (i+1) ==0):
        sumDen = sumDen/(i+1)
        sumNum = sumNum/(i+1)
print sumNum,
print "/",
print sumDen

 

(15)求0—7所能组成的数字中,不重复的8位奇数的个数。

# -*- coding: utf-8 -*-
sum = 1
#从1,3,5,7中选择奇数作为末尾
sum = sum * 4
#选择非0首位
sum = sum * 7
for i in range(6,0,-1):
    sum = sum * i
print sum

 

(16)已有结论“一个偶数总能表示为两个素数之和”,试输入一个偶数,用代码求出它对应的两个素数,若不止一组,尝试求相差最小的一组,比如16=13+3=11+5,则11+5更符合要求。

# -*- coding: utf-8 -*-
def isPrime(num):
    for i in range(2,num):
        if num % i == 0:
            return False
    return True
 
num = input()
temp = num / 2
for i in range(0,temp):
    if( isPrime( temp + i ) and isPrime( temp - i )):
        print temp+i,temp-i
        break;

 

(17) 对一个列表元素进行排序,要求:非冒泡排序法,非内置排序函数。

# -*- coding: utf-8 -*-
 
array = [1,5,5,6,3,6,2,7,9,1,0]
def selectionSort(arr):
    for i in range(0,len(arr)):
        min = i;
        for j in range(i+1,len(arr)):
            if(arr[j] < arr[min]):
                min = j
        if i != min:
            arr[min],arr[i] = arr[i],arr[min]
    return arr
 
print selectionSort(array)

 

(18) 有一个已经排好序的列表。现输入一个数,要求按原来的规律将它插入数组中。(注意,并不知列表原来是什么顺序)

# -*- coding: utf-8 -*-
 
array = [9,5,3,2,1]
 
num = input()
def insertArray(array , num):
    if(len(array) == 0 or len(array) == 1):
        array.append(num)
    else:
        if(array[0] < array[len(array)-1]):
            #升序
            for i in range(0,len(array)-1):
                if(num <= array[0]):
                    array.insert(0,num)
                    break
                elif(num >= array[len(array)-1]):
                    array.append(num)
                    break
                elif(array[i]<num and array[i+1]>=num):
                    array.insert(i+1,num)
        else:
            #降序
            for i in range(0,len(array)-1):
                if (num >= array[0]):
                    array.insert(0, num)
                    break
                elif (num <= array[len(array) - 1]):
                    array.append(num)
                    break
                elif (array[i] > num and array[i + 1] <= num):
                    array.insert(i + 1, num)
 
insertArray(array,num)
print array

 

(19) 一个列表逆序输出。(注意仅逆序输出,不要改变原列表元素)

# -*- coding: utf-8 -*-
 
array = [9,5,3,2,1]
 
for i in range(len(array)-1,-1,-1):
    print array[i],

 

(20) 将一个整数依次按 十六进制、八进制、二进制输出。

# -*- coding: utf-8 -*-
num = input()
print hex(num)
print oct(num)
print bin(num)

 

(21)  写如下几个进制转换函数,实现八进制、十进制、十六进制字符串的互转,不能使用内建转换函数,dec2oct,dec2hex,oct2dec,oct2hex,hex2oct,hex2dec,比如hex2oct(“FF”)==dec2oct(“255”)==”377″。

 

(22)输入整数V和整数m,n(0<=m<n<=31,0是低位),取V的二进制的第m到n位数字。例如:输入52,二进制为:0011 0100,取第3到5位的结果为:011。

# -*- coding: utf-8 -*-
V = input()
m = input()
n = input()
 
a =  str(bin(V))
print a
for i in range(m,n+1):
    print a[len(a)-1-i],

 

(23) 输入一个列表,将列表中最大的数与第一个元素交换,最小的与最后一个元素交换,输出之。

# -*- coding: utf-8 -*-
array = [7,1,5,6,6,2,1,4,8,9,5]
max = 0
min = 0
for i in range(0,len(array)):
    if(array[i] > array[max]):
        max = i
    if(array[i] < array[min]):
        min = i
 
array[max],array[0] = array[0],array[max]
array[min],array[len(array)-1] = array[len(array)-1],array[min]
 
print array

 

(24) 有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。

# -*- coding: utf-8 -*-
n = input()
array = []
count = 0
for i in range(1,n+1):
    array.append(i)
 
while(len(array) > 1):
    q = []
    for i in array:
        count = count + 1
        if(count % 3 != 0):
            q.append(i)
    array = q
 
print  array[0]

 

(25) 创建一个列表,依次输入整形元素并插入列表尾;

(1)反向输出之,

(2)输出其单数列的元素,再输出其双数列的元素

(3)让单数列元素按升序排列,双数列元素按降序排列

# -*- coding: utf-8 -*-
n = input()
array = []
for i in range(0,n):
    temp = input()
    array.append(temp)
 
for i in range(n-1,-1,-1):
    print array[i],
 
print
 
for i in range(0,n):
    if(i % 2 == 0):
        print array[i],
print
 
for i in range(0,n):
    if(i % 2 == 1):
        print array[i],
print
 
for i in range(2,n,2):
    for j in range(i+1,n,2):
        if(array[j] > array[j-2]):
            array[j],array[j-2] = array[j-2],array[j]
 
for i in range(1,n,2):
    for j in range(i+1,n,2):
        if(array[j] < array[j-2]):
            array[j],array[j-2] = array[j-2],array[j]
 
print array

 

(26)创建一个字典,依次输入整形键、值并放入字典中。

1)依次打印键、值

2)以键的升序打印值

3)以值的升序打印键,同值则以键序

4)删除字典中键为1的元素,删除字典中值为1的元素

5)遍历字典,将字典中键为单数的元素都删去

# -*- coding: utf-8 -*-
dict = {}
a = []
b = []
for i in range(0,3):
    a = input()
    b = input()
    dict[a]=b
 
for key in dict.keys():
    print key,dict[key]
 
#以键排序
a = sorted(dict.items(),key = lambda  e:e[0],reverse=False)
#以值排序
b = sorted(dict.items(),key = lambda  e:e[1],reverse=False)
print a
print b
 
#删除字典中键为1的元素
for key in dict.keys():
    if(key == 1):
        dict.pop(1)
 
#删除字典中值为1的元素
for key in dict.keys():
    if(dict[key] == 1):
        dict.pop(key)
 
#普通遍历将字典中键为单数的元素都删去
count = 0
for key in dict.keys():
    if(count % 2 == 0):
        dict.pop(key)
    count = count + 1
 
print dict

 

(27) 编写一个类CPeople,保存着人的姓名str、年龄int、性别bool、工号int;依次从键盘或者文件输入每个人的如上信息。

1)遍历输出所有人的信息,格式为:“姓名:xxx;年龄:xx;性别:男/女;工号:xxxxxx”

2)遍历输出所有男性/女性员工信息,注意列对齐

3)按年龄升序输出所有员工姓名,同年龄则以工号升序为序

4)存储people类对象的数据结构使用list/dict,重新实现上述需求

# -*- coding: utf-8 -*-
class CPeople(object):
 
    def __init__(self , name , age , gender ,number):
        self.name = name
        self.age = age
        self.gender = gender
        self.number = number
 
liu = CPeople("liu",20,True,101)
chen = CPeople("chen",20,True,102)
deng = CPeople("deng",21,True,104)
yang = CPeople("yang",21,True,103)
tian = CPeople("tian",20,True,105)
xia = CPeople("xia",20,False,106)
 
arr = [liu,chen,yang,deng,tian,xia]
for i in arr:
    print i.name,i.age,i.gender,i.number
 
#输出男性
print "BOY:"
for i in arr:
    if(i.gender):
        print i.name,i.age,i.gender,i.number
 
#输出女性
print "GIRL:"
for i in arr:
    if(i.gender == False):
        print i.name,i.age,i.gender,i.number
 
#按年龄升序输出所有员工姓名,同年龄则以工号升序为序
try:
    import  operator
except ImportError:
    cmpfun = lambda CPeople:CPeople.age
else:
    cmpfun = operator.attrgetter("age","number")
 
    arr.sort(key = cmpfun , reverse = False)
    for i in arr:
        print  i.name

 

(28) 某个公司采用公用电话传递数据,数据是四位的整数,在传递过程中是加密的,加密规则如下:

每位数字都加上5,然后用和除以10的余数代替该数字,再将第一位和第四位交换,第二位和第三位交换。

写出其加密、解密函数。

# -*- coding: utf-8 -*-
data = 1007
#加密函数
def encryptionFun(num):
    num1 = num/1000
    num2 = num/100 % 10
    num3 = num/10 %10
    num4 = num % 10
    num1 = (num1 + 5) % 10
    num2 = (num2 + 5) % 10
    num3 = (num3 + 5) % 10
    num4 = (num4 + 5) % 10
    num1,num4 = num4,num1
    num2,num3 = num3,num2
    return num1*1000+num2*100+num3*10+num4
 
#解密函数
def decodeFun(num):
    num1 = num / 1000
    num2 = num / 100 % 10
    num3 = num / 10 % 10
    num4 = num % 10
    num1, num4 = num4, num1
    num2, num3 = num3, num2
    num1 = (num1 + 10 - 5)%10
    num2 = (num2 + 10 - 5)%10
    num3 = (num3 + 10 - 5)%10
    num4 = (num4 + 10 - 5)%10
    return num1*1000+num2*100+num3*10+num4
 
 
print encryptionFun(data)
print decodeFun(encryptionFun(data))

 

(29) 输入一个字符串,一个子串,计算字符串中子串出现的次数,已匹配过的字符不能再算做下一次匹配字符中。例如”abababab”, “abab” -> 2。

# -*- coding: utf-8 -*-
str= "abababab"
substr = "abab"
 
count = 0
i = 0
while(i <= len(str)-1):
    if(str.find(substr, i, len(str) ) != -1):
        count = count + 1
        i = i + len(substr)
    else:
        i = i + 1
print count

 

(30) 输入一个字符串,出现频率最高的3个字。

# -*- coding: utf-8 -*-
text ="系统初始为Win7.64bit系统,每个项目有特定的操作系统环境需求,具体请咨询所属项目同事;如需调整默认启动系统,请在Win7系统下进行如下操作(必须在Win7系统下才能设置):计算机(右键)-属性-高级系统设置-高级-启动和故障恢复(设置)-默认操作系统"
dict = {}
for word in text:
    if word not in dict:
        dict[word] = 1
    else:
        dict[word] = dict[word] + 1
b = sorted(dict.items(),key = lambda  e:e[1],reverse=True)
print(b)

 

(31) lst = [8,5,0,2,4,6,9,1,3,7],输入一个由0~9组成的列表,将其排序,要求lst位置靠前的元素,其排序后位置同样靠前。

# -*- coding: utf-8 -*-
lst = [8,5,0,2,4,6,9,1,3,7]
list = [0,1,2,3,4,5,6,7,8,9]
dict = {}
count = 0
for i in lst:
    dict[i] = count
    count = count + 1
 
for i in range(0,len(list)):
    for j in range(1,len(list)):
        if(dict[list[j]]<dict[list[j-1]]):
            list[j],list[j-1] = list[j-1],list[j]
 
print (list)

 

(32)在键盘上,左手每隔2秒按下一个字母键,依次循环按下A-Z,右手每隔5秒按下一个数字键,依次循环按下0-9,写代码模拟求按下的第100个键,是那个手?按下的哪个键?

# -*- coding: utf-8 -*-
a = 'A'
b = '1'
count = 0
second = 0
press = ''
 
while(True):
    if(second % 2 == 0):
        press = a
        a = chr(ord(a)+1)
        count = count + 1
 
    if(second % 5 == 0):
        press = b
        b = chr(ord(b)+1)
        count = count + 1
 
    second = second + 1
 
    if(count == 100):
        break
 
print(press,end="")
print("键")
if(press > 'A' and press < 'Z'):
    print("左手")
else:
    print("右手")

 

(33)有如下字典,记录每个地图场景能去往哪个地图场景

DATA = {

“中州城”   : (“师道殿”, “云梦泽”, “逐风原”, “清水湾”, “千魂塔一层”, “帮派地图”, ),

“北漠城”   : (“鸣沙洲”, “百花谷”, ),

“月牙湾”   : (“云梦泽”, “伏波港”, ),

“伏波港”   : (“月牙湾”, “百花谷”, ),

“鸣沙洲”   : (“北漠城”, “苍茫山”, ),

“逐风原”   : (“平安镇”, “中州城”, ),

“百花谷”   : (“北漠城”, “伏波港”, ),

“千魂塔一层”  : (“千魂塔二层”, “中州城”, ),

“云梦泽”   : (“月牙湾”, “中州城”, ),

“苍茫山”   : (“鸣沙洲”, ),

“清水湾”   : (“中州城”, “平安镇”, ),

“师道殿”   : (“绝情谷”, “真武门”, “蛮王殿”, “中州城”, “药王宗”, “天策府”, “拜火教”, “清虚观”, ),

“清虚观”   : (“师道殿”, ),

“天策府”   : (“师道殿”, ),

“真武门”   : (“师道殿”, ),

“拜火教”   : (“师道殿”, ),

“绝情谷”   : (“师道殿”, ),

“蛮王殿”   : (“师道殿”, ),

“药王宗”   : (“师道殿”, ),

“千魂塔二层”  : (“千魂塔一层”, ),

“平安镇”   : (“清水湾”, “逐风原”, ),

“帮派地图” : (“中州城”, ),

}

 

写一个函数FindPath(source, target),返回一个list,元素为从source到target所经过的各个地图名的一条即可。

# -*- coding: utf-8 -*-
DATA = {
   "中州城"  : ("师道殿", "云梦泽", "逐风原", "清水湾", "千魂塔一层", "帮派地图", ),
   "北漠城"  : ("鸣沙洲", "百花谷", ),
   "月牙湾"  : ("云梦泽", "伏波港", ),
   "伏波港"  : ("月牙湾", "百花谷", ),
   "鸣沙洲"  : ("北漠城", "苍茫山", ),
   "逐风原"  : ("平安镇", "中州城", ),
   "百花谷"  : ("北漠城", "伏波港", ),
   "千魂塔一层"    : ("千魂塔二层", "中州城", ),
   "云梦泽"  : ("月牙湾", "中州城", ),
   "苍茫山"  : ("鸣沙洲", ),
   "清水湾"  : ("中州城", "平安镇", ),
   "师道殿"  : ("绝情谷", "真武门", "蛮王殿", "中州城", "药王宗", "天策府", "拜火教", "清虚观", ),
   "清虚观"  : ("师道殿", ),
   "天策府"  : ("师道殿", ),
   "真武门"  : ("师道殿", ),
   "拜火教"  : ("师道殿", ),
   "绝情谷"  : ("师道殿", ),
   "蛮王殿"  : ("师道殿", ),
   "药王宗"  : ("师道殿", ),
   "千魂塔二层"    : ("千魂塔一层", ),
   "平安镇"  : ("清水湾", "逐风原", ),
   "帮派地图" : ("中州城", ),
}
 
lst = []
def FindPath(source ,target):
    if(source == target):
        return lst
    elif(target in lst):
        flag = True
        return lst
    for i in DATA[source]:
        if(i in lst):
            break
        else:
            lst.append(i)
            if(target in FindPath(i,target)):
                return lst
 
    return lst
 
list = FindPath("平安镇","中州城")
print(list)

 

(34) 有如下字符串

s = “””师门任务20次,0,80

除魔任务20次,0,100

闹事妖怪10次,0,50

运镖任务5次,0,40

挖宝5次,0,40

角色升级1次,0,50

完成4次江湖悬赏令,10,40

任务链整百环3次,0,90

获得修炼经验400点,0,50

野外暗雷战斗60次,0,50″””

将如上字符串解析为如下格式,注意对齐方式,以及第一项“今天总计”并不出现在s中,而是各行数字计算值。

# -*- coding: utf-8 -*-
import  re
s = """
   师门任务20次,0,80
   除魔任务20次,0,100
   闹事妖怪10次,0,50
   运镖任务5次,0,40
   挖宝5次,0,40
   角色升级1次,0,50
   完成4次江湖悬赏令,10,40
   任务链整百环3次,0,90
   获得修炼经验400点,0,50
   野外暗雷战斗60次,0,50"""
lst =  (re.findall(r"\d+",s))
 
#计算总数
count = 0
sum1 = 0
lst1 = []
sum2 = 0
lst2 = []
for i in lst:
    if (count % 3 == 1):
        sum1 = sum1 + int(i)
        lst1.append(i)
    elif (count % 3 == 2):
        sum2 = sum2 + int(i)
        lst2.append(i)
    count = count + 1
lst1.insert(0,str(sum1))
lst2.insert(0,str(sum2))
 
s1 = list(s)
count = 0
for i in range(0,len(s1)):
    if(s1[i] is ","):
        if(count % 2 == 0):
            s1[i] = ":"
            count = count + 1
        else:
            s1[i] = "/"
            count = count + 1
s = ''.join(s1)
s1 = re.split("\n\t|:",s)
 
count = 0
res = []
res.append("今天总计:")
for i in range(0,len(s1)):
    if(count % 2 == 0):
        count = count + 1
    else:
        res.append(s1[i])
        count = count + 1
 
 
print(" 每天完成以下事项可得活跃度")
tplt = "{0:{1}>10}"
for i in range(0,len(res)):
    print(tplt.format(res[i],chr(12288)),end="")
    print(":",end="")
    print(lst1[i],end="")
    print("/",end="")
    print(lst2[i])

 

(35)举例说明python中可变类型与不可变类型都有哪些?

不可变类型:数字、字符串、元组

可变类型:列表、字典

 

(36)编写函数,检测给定的两维列表中是否有重复数据(已知该列表中保存的是正整数):check_data(lList),如果没有重复,则函数返回真。要求算法的时间复杂度不大于O(n)。

# -*- coding: utf-8 -*-
lst1 = [['apple','banana','orange'],
        ['rabbit','tiger','forg'],
        ['microsoft','apple','amazon'],
        ['intel','amd']]
 
def check_data(List):
    map = {}
    for i in List:
        for j in i:
            if(j not in map):
                map[j] = 1
            else:
                return False
    return True
 
print(check_data(lst1))

 

Linux一切皆文件

和 Windows 系统不同,Linux 系统没有 C 盘、D 盘、E 盘那么多的盘符,只有一个根目录(/),所有的文件(资源)都存储在以根目录(/)为树根的树形目录结构中。
这样做最明显的好处是,开发者仅需要使用一套 API 和开发工具即可调取 Linux 系统中绝大部分的资源。举个简单的例子,Linux 中几乎所有读(读文件,读系统状态,读 socket,读 PIPE)的操作都可以用 read 函数来进行;几乎所有更改(更改文件,更改系统参数,写 socket,写 PIPE)的操作都可以用 write 函数来进行。

不利之处在于,使用任何硬件设备都必须与根目录下某一目录执行挂载操作,否则无法使用。我们知道,本身 Linux 具有一个以根目录为树根的文件目录结构,每个设备也同样如此,它们是相互独立的。如果我们想通过 Linux 上的根目录找到设备文件的目录结构,就必须将这两个文件系统目录合二为一,这就是挂载的真正含义。

 

远程服务器关机及重启时的注意事项

为什么远程服务器不能关机?原因很简单,远程服务器没有放置在本地,关机后谁帮你按开机电源键启动服务器?虽然计算机技术曰新月异,但是像插入电源和开机这样的工作还是需要手工进行的。如果服务器在远程,一旦关机,就只能求助托管机房的管理人员帮你开机了。

远程服务器重启时需要注意两点。

1) 远程服务器在重启前,要中止正在执行的服务

计算机的硬盘最怕在高速存储时断电或重启,非常容易造成硬盘损坏。所以,在重启前先中止你的服务,甚至可以考虑暂时断开对外提供服务的网络。

可能你会觉得服务器有这么娇贵吗?我的笔记本电脑经常强行关机,也没有发现硬盘损坏啊?这是因为你的个人计算机没有很多人访问,强制断电时硬盘并没有进行数据交换。小心驶得万年船!

2) 重启命令的选用

Linux 可以识别的重启命令有很多条,但是建议大家使用 “shutdown-r now” 命令重启。这条命令在重启时会正常保存和中止服务器中正在运行的程序,是安全命令。

最好在重启前执行几次 “sync” 命令,这条命令是数据同步命令,可以让暂时保存在内存中的数据同步到硬盘上。

重启和关机也是服务器需要注意的操作规范,不正确的重启和关机造成服务器故障的不在少数。

 

常见命令

cd 命令,是 Change Directory (改变目录)的缩写,用来切换工作目录。

pwd 命令,是 Print Working Directory (打印工作目录)的缩写,功能是显示用户当前所处的工作目录。

ls 命令,list 的缩写,是最常见的目录操作命令,其主要功能是显示当前目录下的内容。

mkdir 命令,是 make directories 的缩写,用于创建新目录,此命令所有用户都可以使用。

和 mkdir 命令(创建空目录)恰好相反,rmdir(remove empty directories 的缩写)命令用于删除空目录。

既然知道了如何在 Linux 系统中创建目录,接下来你可能会想在这些目录中创建一些文件,可以使用 touch 命令。需要注意的是,touch 命令不光可以用来创建文件(当指定操作文件不存在时,该命令会在当前位置建立一个空文件),此命令更重要的功能是修改文件的时间参数(但当文件存在时,会修改此文件的时间参数)。

cp 命令,主要用来复制文件和目录,同时借助某些选项,还可以实现复制整个目录,以及比对两文件的新旧而予以升级等功能。

rm 是强大的删除命令,它可以永久性地删除文件系统中指定的文件或目录。在使用 rm 命令删除文件或目录时,系统不会产生任何提示信息。

mv 命令(move 的缩写),既可以在不同的目录之间移动文件或目录,也可以对文件和目录进行重命名。

cat 命令可以用来显示文本文件的内容(类似于 DOS 下的 type 命令),也可以把几个文件内容附加到另一个文件中,即连接合并文件。

more 命令可以分页显示文本文件的内容,使用者可以逐页阅读文件中内容。

less 命令的作用和 more 十分类似,都用来浏览文本文件中的内容,不同之处在于,使用 more 命令浏览文件内容时,只能不断向后翻看,而使用 less 命令浏览,既可以向后翻看,也可以向前翻看。

 

Linux 系统中,每个文件主要拥有 3 个时间参数(通过 stat 命令进行查看),分别是文件的访问时间、数据修改时间以及状态修改时间:

  • 访问时间(Access Time,简称 atime):只要文件的内容被读取,访问时间就会更新。例如,使用 cat 命令可以查看文件的内容,此时文件的访问时间就会发生改变。
  • 数据修改时间(Modify Time,简称 mtime):当文件的内容数据发生改变,此文件的数据修改时间就会跟着相应改变。
  • 状态修改时间(Change Time,简称 ctime):当文件的状态发生变化,就会相应改变这个时间。比如说,如果文件的权限或者属性发生改变,此时间就会相应改变。

qmake简介

qmake是Qt的构建工具,主要作用是解析pro格式的项目文件、生成编译规则(Makefiles或其它)。

qmake是一个比较古老的工具,很多功能使用perl脚本实现。

Qt官方之前开发的Qbs,后来又宣布不再更新,现在又大力支持CMake。

在这样的背景下,qmake依然是当下主要的构建工具,所以qmake的一些技巧还是有必要掌握的。

qmake本身作为一个可执行程序,也是有一些参数的,但这不是本文的重点,本文的重点都在pro文件里。

pro文件中,除了常规的组织项目结构外,还可以做很多事情, 比如 指定编译选项、链接选项、制定目标生成规则、扩展编译规则 等等。

pro文件中的qmake语法,包括 变量声明和使用、内建变量、替换函数、测试函数等,帮助文档都有详细的介绍。

添加第三方库

在C++开发,使用第三方库也是家常便饭了,这是一个必备的技能。

这里首选的方法,是使用QtCreator提供的添加库功能。在pro文件里(或者项目文件夹), 鼠标右键->添加库,然后根据自己的需要下一步、下一步点一下即可。

熟练的人也可以直接按pro语法(perl语法)写,给LIBS变量赋值。

  • 直接使用链接库的全路径
  LIBS += c:/mylibs/XXX.lib

我们都知道windows系统默认的路径分割符是\,但在qmake中要写成\才行。qmake也支持写成’/’,其它unix系统又都是’/’,所以干脆都写成’/’,方便处理。

  • 路径中包含空格等特殊字符,用引号括起来
  LIBS += "C:/mylibs/xxx libs/XXX.lib"
  • 分别指定路径和库
  LIBS += "-LC:/mylibs/xxx libs" -lxxx

这里的LIBS指定要链接的库,’-L’是指定链接库的路径,’-l’指定要链接的库名称。
名称可以省略lib前缀和 扩展名后缀,Qt会自动处理。拓展名包括 ‘.so’ ‘.dll’ ‘.dylib’ 等。

  • 分平台条件链接
  win32:LIBS += "C:/mylibs/xxx libs/xxx.lib"
  unix:LIBS += "-L/home/user/xxx libs" -lxxx

条件链接可以很方便地实现不同平台链接不同的库。
这里的 win32 unix 是在选择了不同的编译器环境时,qmake分别预置的变量。

原理

Qt内置了一些perl脚本,在执行qmake解析时会包含这些脚本。其中一些脚本会来处理这个LIBS变量,将其转换成编译器/链接器的参数。

内置的脚本路径在[QTDIR]/mkspecs/features文件夹下,扩展名为prf。

后续的很多变量,也是一样的原理, 只是处理方式各不相同。

很多pro文件的语法、功能实现,都可以参考这些prf来实现。

Qt程序员都知道的一件事:有时候修改了信号/槽相关的代码,不能正常运行,要重新qmake一下,才会生效。

本质上就是在重新触发[QTDIR]/mkspecs/features/moc.prf这个脚本。

影子构建

影子构建,就是编译生成的产物和源代码在不同的文件夹。这样可以防止源代码文件夹被污染。

QtCreator默认导入pro工程时,就会生成一个影子构建路径。比如这样:

F:\Dev\Qt\Desktop_Qt_5_12_3_MSVC2017_64bit-Debug

之后编译项目时生成的中间文件及目标文件,都在这个文件夹中。

这个路径很长,而且编译器或者编译选项不同时都有可能不一样。

有时候要做一些特定的操作:比如目标exe生成到特定目录、拷贝资源文件等等,直接用这个路径会不太方便/不太可靠,我们需要一些定制。

指定目标路径

  DESTDIR = $$PWD/bin

通过给DESTDIR变量赋值, 可以指定生成的lib/exe放在哪个目录下

‘PWD’是qmake内置变量,’$$‘是内置变量取值的写法。’/bin’是字符串拼接在变量后面。

指定中间件生成路径

可以通过这几个变量指定中间件生成的路径

config(debug, debug|release) {
    OBJECTS_DIR = build/debug/obj
    MOC_DIR = build/debug/moc
    RCC_DIR = build/debug/rcc
    UI_DIR = build/debug/uic
} else {
    OBJECTS_DIR = build/release/obj
    MOC_DIR = build/release/moc
    RCC_DIR = build/release/rcc
    UI_DIR = build/release/uic
}

config(debug, debug|release) 是一个条件表达式,可以理解为

if (debug === true) {

} else if (release == true) {

}

注意: 按照perl语法,那个左大括号’{‘不能换行,要和前面的表达式在同一行。

上面这种指定中间件路径的方式,在QtCreator中有默认路径所以没有太大意义,不过在命令行编译时这样写却很有用。

内容:

第一章

我们首先看一下组成PDF文件的各种对象,以及它们是如何结合在一起的。

第二章

在本章中,我们将讨论PDF的核心方面——它的成像模型。我们学习如何创建页面并在其上绘制一些图形。

第三章

继续对核心成像模型的讨论,在本章中我们将探讨如何将光栅图像合并到您的PDF内容中。

第四章

接下来,我们将学习如何合并最后一种常见的PDF内容——文本类型。当然,如果没有字体和象形文字,PDF格式的文本讨论是不完整的。

第五章

PDF不仅仅是静态内容。本章将介绍PDF可以获得交互性的各种方法,特别是围绕在文档内部和文档之间启用导航的方式。

第六章

本章探讨注释的特殊对象,这些对象是在常规内容的基础上绘制的,以支持从交互链接到3D到视频和音频的所有内容。

第七章

接下来,我们将讨论如何在PDF语言中提供交互式表单。

第八章

本章演示如何通过在PDF中嵌入文件,以类似于ZIP存档的方式使用PDF。

第九章

本章解释如何将视频和音频内容作为丰富内容的一部分引用到PDF中或嵌入到PDF中。

第十章

本章介绍了可选内容,这些内容仅在特定时间出现,例如在屏幕上,而不是打印时或仅针对某些用户。

第十一章

本章讨论如何通过使用类似HTML的结构(如段落和表)来为内容添加语义丰富。

第十二章

本章探讨了将元数据合并到PDF文件的各种方法,从最简单的文档级别字符串到附加到indi-vidued对象的富XML。

第十三章

最后,本章介绍了基于PDF的各种开放国际标准,包括完整的PDF标准本身(iso 32000-1)、各种子集(如PDF/A和PDF/X)以及 相关工作(如PAdES)。

 

第一章

我们将直接进入PDF文件格式的构建块开始我们对PDF的探索。使用这些块,您将看到PDF是如何构造成基于页面的格式的。

PDF对象

PDF文件的核心部分是PDF标准(Iso 32000)所指的“事物”集合,有时也称为COS对象。

这个对象不是“面向对象编程”这个词意义上的对象;相反,它们是PDF所赖以生存的基石。有九种类型的对象:null,boolean, integer, real, name, string, array, dictionary, and stream.

分别为空、布尔、整数、实数、名称、字符串、数组、字典和流。

让我们看看这些对象类型中的每一种,以及它们是如何序列化成PDF文件的。然后,您将看到如何接受这些对象类型,并使用它们构建更高级别的构造和 PDF格式本身。

Null Objects(空对象)

如果实际写入文件,则NULL对象就是四个简单的NULL字符。它等同于一个缺失值,这就是它为什么在PDF中很少看到的原因。如果你有机会与空值一起工作,请确保仔细地品味ISO 32000中涉及其处理的微妙之处。

Boolean Objects(布尔对象)

布尔对象表示为true和false的逻辑值,相应的在PDF中也是,既可以为true,也可以为false。

在编写PDF时,您将始终使用true或false。但是,如果您正在阅读/解析PDF并且希望能够容忍,请注意写得不好的PDF可能会使用其他的大写形式,包括首字母大写(True或False)或全部大写(TRUE或FALSE)。

Numeric Objects(数字对象)

PDF支持两种不同类型的数字对象——整型和实形——来表示它们的数学等价物。虽然旧版本的PDF已经声明实现了与Adobe以前的实现相匹配的限制,但这些不应该再被视为文件格式的限制(也不应该被任何特定的实现所限制)。

虽然PDF支持64位数字(以便启用非常大的文件),但您会发现大多数PDF实际上并不需要它们。然而,如果你正在阅读PDF,你可能真的会遇到他们,所以请做好准备。

整数数字对象由一个或多个十进制数字组成,可以选择前面加上一个符号,表示一个有符号的值(10进制表示)。示例1-1显示了一些整数的例子。

Example 1-1. Integers

1
-2
+100
612

 

实数数字对象由一个或多个十进制数字组成,其中包含一个可选符号和一个前导、尾随或嵌入的句点,表示一个有符号的实值。与PostScript不同,PDF不支持 科学/指数格式,也不支持非十进制。

虽然在PDF中使用了术语“real”来表示对象类型,但是给定查看器的实际实现可能使用double、float甚至定点数。因为实现可能会有所不同,小数位的精度可能也不一样。因此,为了可靠性和文件大小的考虑,建议不要写超过小数点的四位。

示例1-2显示了一些在PDF中实数是什么样子的示例。

Example 1-2. Reals

0.05
.25
-3.14159
300.9001

 

Name Objects(名字对象)

PDF中的名字对象是唯一的字符序列(字符代码0除外,ASCII NULL除外),通常在有固定值集的情况下使用。姓名被写入PDF格式时,带有一个转义“/”字符,后面跟着一个UTF-8字符串,对任何非规则字符都有一个特殊的编码形式。非规则字符是那些定义在0x21(!)到0x7e(~)范围外的字符, 以及任何空白字符(见表1-1)。这些非规则字符以#(数字符号)开始编码,然后是字符的两位十六进制代码。

由于其独特的性质,您将写入PDF的大多数名称都是在ISO 32000中预先定义的,或者是从外部数据(例如字体或颜色名称)派生出来的。

如果您需要创建自己的非外部数据自定义名称(例如私有元数据),如果您希望您的文件被视为有效的PDF,则必须遵循ISO 32000-1:2008附件E中定义的二等名称规则。第二个类名以四个字符的ISO注册前缀开头,后面跟着下划线(_),然后是键名。一个例子包括在示例1-3的末尾。

Example 1-3. Names

/Type
/ThisIsName37
/Lime#20Green
/SSCN_SomeSecondClassName

 

String Objects(字符串对象)

字符串被序列化为PDF格式,它们只是一系列(0或更多个)8比特字节,这些字节要么是用括号括起来的文字字符,要么是用尖括号括起来的十六进制数据。

一个文本字符串包含任意数量的8比特字符,这些字符被括在括号中。因为任何8位值都可能出现在字符串中,所以单边的括号

和反斜杠是通过使用反斜杠来进行特殊转义处理的特殊值。此外,反斜杠可以与特殊的\ddd符号一起使用以指定其他字符值。

前面关于字符串的讨论是关于如何将值序列化为PDF文件,而不一定是PDF处理器如何在内部处理这些值。当这样的内部处理结束时 在标准的范围内,重要的是要记住,不同的文件序列化可以产生相同的内部表示(例如(A\053 B)和(A B),在示例1-4中)。

 

文字字符串有几个不同的变体:

ASCII:只包含ASCII字符的字节序列。

PDFDocEncoded:按照PDFDocEncode编码的字节序列(ISO 32000-1:2008,7.9.2.3)。

Text:编码为PDFDocEncoding或UTF-16BE(带有前导字节顺序标记)的字节序列。

Date:格式为D:YYYYMMDDHHmmSSOHH’mm的ASCII字符串(ISO 32000-1:2008,7.9.4)。

日期作为字符串的一种类型,在1.1版中添加到PDF中。

这对于在字符串对象中包含更多人类可读的任意二进制数据或Unicode值(UCS-2或UCS-4)非常有用。数字的数目位数必须始终为偶数,可以在数字对之间添加空白字符,以提高人的可读性。

示例1-4在PDF中显示了几个字符串示例。

Example 1-4. Strings

(Testing) % ASCII
(A\053B) % 形如 (A+B)
(Français) % PDFDocEncoded
<FFFE0040> % Text with leading BOM
(D:19990209153925-08'00') % Date
<1C2D3F> %任意二进制数据

 

百分比符号(%)表示注释,它后面的任何文本都会被忽略。

前面关于字符串的讨论是关于如何将值序列化为PDF文件,而不一定是PDF处理器如何在内部处理这些值。同时这样的内部处理超出了标准的范围,记住不同的文件序列化可以产生相同的内部表示这一点很重要。(例如A\053B)和(A+B)(在实例1-4中)

Array Objects(数组对象)

数组对象是包含在方括号([和])中并由空白分隔的其他对象的异构集合。你可以将任意类型的对象混合和匹配在一个数组里,PDF在很多地方都利用了这一点。数组也可以是空的(即包含零元素)。

当一个数组只包含一个一维时,就可以构造一个多维数组的等价物。这个结构在PDF中不经常使用,但它确实使用出现在一些地方,例如数据结构中的顺序数组,称为可选内容组词典。

PDF数组中的元素数没有限制。但是,如果您找到了一个可以替代大规模数组的方法(例如单个孩子结点数组的页面树),那么最好避免使用它们。

在例子1-5中给出了数组的一些例子。

Example 1-5. Arrays

[ 0 0 612 792 ] % 全是整数的4个元素数组
[ (T) –20.5 (H) 4 (E) ] % 由string(字符串),real(实型),integer(整数)组成的5个元素的数组
[ [ 1 2 3 ] [ 4 5 6 ] ] % 由2个数组元素构成的数组

 

Dictionary Objects(字典对象)

由于它是几乎所有高级对象的基础,PDF中最常见的对象是字典对象。它是键/值对的集合,也称为关联表。每个键总是一个名字对象(Name Objects),但该值可能是任何其他类型的对象,包括另一个字典,甚至NULL。

当值为NULL时,它被视为该键不存在。因此,最好不要写这种键,以便节省处理时间和空间大小。

字典用双尖括号(<<和>>)括起来。在这些括号内,键可以按任何顺序显示,紧跟它们的是值。哪些键出现在字典中由正在被创作的高级对象的定义(在ISO 32000中)确定。

虽然许多现有的实现倾向于按字母顺序编写键,但这既不是必须的,也不是被期望的。实际上,不应该对字典处理做出任何假设 ——可以按任何顺序读取和处理键。包含相同键两次的字典无效,对应的值未定义。最后,虽然在键/值对之间换行提高了人类的可读性,但这也不是必需的,只会增加文件的总大小。

字典中的键/值对的数量没有限制。

示例1-6显示了一些示例。

Example 1-6. Dictionaries

% 一个更具可读性的字典。
<<
/Type /Page
/Author (Leonard Rosenthol)
/Resources << /Font [ /F1 /F2 ] >>
>>
% 一个删掉所有空格的字典
<</Length 3112/Subtype/XML/Type/Metadata>>

 

Name trees

名称树的用途类似于字典,因为它提供了将键与值相关联的方法。但是,与字典中不同的是,键是字符串对象,而不是名字对象,它们是按标准Unicode排序规则算法排序的。

这个概念被称为名称树,因为有一个“根”字典(或节点)引用一个或多个子字典/节点,它们本身可以引用一个或多个子字典/节点。,从而创建树状结构的许多分支。

根节点保存一个键,这个键可以是任意一个名称(用于简单树)或子节点(用于更复杂的树)。在复杂树的情况下,每个中间节点都有一个子节点的键,每个分支的最终节点将包含名称键。它是Names键的数组值,通过交替键/值指定键及其值,如例1-7所示。

Example 1-7. 只有几个名字的简单名字树

%  Simple name tree with just some names
1 0 obj
<<
/Names [
(Apple) (Orange) % 这些都是排好序的,从A到Z.
(Name 1) 1 % 值可以是任何类型
(Name 2) /Value2
(Zebra) << /A /B >>
]
>>
endobj

 

Number trees

数字树类似于名称树,只不过它的键是整数而不是字符串,并且按升序排序。同时,叶(或根)节点中包含键/值对为数字键的值,而不是名字键的值。

Stream Objects(流对象)

PDF中的流是8位字节的任意序列,可以是无限长度的,并且可以压缩或编码。因此,它们是用于存储其他标准化格式(如XML语法、字体文件和图像数据)的大数据块的对象类型。

流对象由对象的数据表示,该数据由包含流的属性的字典前面的数据表示,称为流字典。使用单词流(后面跟着行结束标记)和尾流(前面是行尾标记)有助于从其字典中描述流数据,同时也使它区别于一个标准字典对象。流字典从不单独存在;它始终是流对象的一部分。

流字典总是包含至少一个键长度,该键表示从流后一行的开始到最后一个在结束流前面的行字符结尾之前的字节的字节数。换句话说,它是序列化成PDF文件的实际字节数。在压缩流的情况下,它是压缩字节数。虽然通常不提供,但原始的未压缩长度可以指定为DL键的值。(DL key意义不明)

流字典中最重要的键之一是过滤键,当原始数据还没有被包括到流中的时候,它可以指定对原始数据的压缩或编码(如果有)。使用FlateDecode过滤器压缩大型图像和嵌入式字体是很常见的,而FlateDecode过滤器使用的技术与ZIP文件格式所使用的无损COM-压缩技术相同。对于图像,两个最常见的过滤器是生成一个JPEG/JFIF兼容流的DCTDecode,以及生成一个JPEG 2000兼容流的JPXDe代码。其他过滤器可在ISO 32000-12008的表6中找到。示例1-8显示了PDF中的流对象可能是什么样子。

Example 1-8. 一个流的例子

<<
 /Type /XObject
 /Subtype /Image
 /Filter /FlateDecode
 /Length 496
 /Height 32
 /Width 32
>>
stream
%  496字节的平面编码数据在这里...
endstream

Direct versus Indirect Objects(直接对象与间接对象)

现在您已经了解了对象的类型,了解这些对象可以直接或间接地在PDF中表示是很重要的。

直接对象是那些在从文件中读取对象时直接获得的“内联”对象。它们通常存在于字典键的值中、或者数组中的条目,并且对象类型是你到目前为止在所有示例中看到过的对象类型。

间接对象是指通过引用和PDF阅读器不得不间接跳转文件才能以找到实际的值的对象。为了验证哪个对象被引用,每个间接对象在每个PDF中都有一个唯一的ID,它表示为一个正数,和一个代数,这个代数总是一个非负数,通常是零(0)。这些数字既用于定义对象,也用于引用对象。

虽然代数最初打算用作跟踪PDF版本的方法,但是现代PDF系统几乎从不使用生成号,因此它们几乎总是为零。

要使用间接对象,首先必须使用ID和代数以及obj和endobj关键字来定义它,如例1-9所示。

Example 1-9. 完全由直接对象构成的间接对象

3 0 obj % 对象ID号为3, 代数为0
<<
 /ProcSet [ /PDF /Text /ImageC /ImageI ]
 /Font <<
 /F1 <<
 /Type /Font
 /Subtype /Type1
 /Name /F1
 /BaseFont/Helvetica
 >>
 >>
>>
endobj
5 0 obj
(an indirect string)
endobj
% 一个直接数字
4 0 obj
1234567890
endobj

 

当您引用一个间接对象时,可以使用它的ID、它的代数和字符R。例如,可以看到类似于示例1-10这样的东西,其中有两个间接对象(ID号为4和5)的参考文献。

Example 1-10. 一个引用其他间接对象的间接对象

3 0 obj % 对象ID号为3, 代数为0
<<
 /ProcSet 5 0 R % 引用ID号为5,代数为0的直接对象
 /Font <</F1 4 0 R >> % 引用ID号为4,代数为0的直接对象
>>
endobj
4 0 obj % 对象ID号为4,代数为0
<<
 /Type /Font
 /Subtype /Type1
 /Name /F1
 /BaseFont/Helvetica
>>
endobj
5 0 obj % 对象ID号为5,代数为0
[ /PDF /Text /ImageC /ImageI ]
endobj

 

通过使用ID号和代数的组合,可以在给定的PDF中唯一地标识每个对象。使用PDF的交叉参考表功能,可以很容易地找到每个间接对象并按要求从参考书加载。

除非ISO 32000中另有说明,否则在使用对象时,它可以是任意类型的——但流除外,后者只能是间接的。

File Structure(文件结构)

如果要在PDF查看器中查看一个简单的PDF文件(我们称之为HelloWorld.pdf),它将如图1-1所示

图1-1.Hello World.pdf

但是,如果要在文本编辑应用程序中查看HelloWorld.pdf,它将类似于示例1-11。

Example 1-11.在文本编辑器中“HelloWorld d.pdf”是什么样子?

%PDF-1.4
%%EOF
6 0 obj
<<
 /Type /Catalog
 /Pages 5 0 R
>>
endobj
1 0 obj
<<
 /Type /Page
 /Parent 5 0 R
 /MediaBox [ 0 0 612 792 ]
 /Resources 3 0 R
 /Contents 2 0 R
>>
endobj
4 0 obj
<<
 /Type /Font
 /Subtype /Type1
 /Name /F1
 /BaseFont/Helvetica
>>
endobj
2 0 obj
<<
 /Length 53
>>
stream
BT
 /F1 24 Tf
 1 0 0 1 260 600 Tm
 (Hello World)Tj
ET
endstream
endobj
5 0 obj
<<
 /Type /Pages
 /Kids [ 1 0 R ]
 /Count 1
>>
endobj
3 0 obj
<<
 /ProcSet[/PDF/Text]
 /Font <</F1 4 0 R >>
>>
endobj
xref
0 7
0000000000 65535 f
0000000060 00000 n
0000000228 00000 n
0000000424 00000 n
0000000145 00000 n
0000000333 00000 n
0000000009 00000 n
trailer
<<
 /Size 7
 /Root 6 0 R
>>
startxref
488
%%EOF

 

看到上面的例子,您可能会得到错误的印象,即PDF文件是一个文本文件,可以使用文本编辑器进行常规编辑——不!PDF文件是一个结构化的8位二进制文档,由一系列基于8位字符的标记描述,由空格分隔,排列成(任意长的)行。这些标记不仅用于描述各种对象及其类型,正如您在上一节中所看到的,而且还可以定义PDF的四个逻辑部分开始和结束的位置。(见图1-2.)

如前所述,PDF中的标记总是以ASCII中的8位字节编码(并因此解码)。它们不能以任何其他方式进行编码,例如Unicode。当然,特定的数据或对象值可以用Unicode编码;我们将在出现这些情况时再讨论它们。

White-Space(空白)

表1-1中所示的空格字符在PDF中被用来分隔句法结构,例如名称和数字。

Table 1-1. 空白字符

十进制 十六进制 八进制 名字
0 00 000 NULL(NUL)
9 09 011 HORIZONTAL TAB(HT)
10 0A 014 LINE FEED(LF)
12 0C 014 FORM FEED(FF)
13 0D 015 CARRIAGE RETURN(CR)
32 20 040 SPACE(SP)

在除注释、字符串、交叉引用表条目和流以外的所有上下文中,PDF将任何连续空格字符序列视为一个字符。

回车(0DH)和换行(0Ah)字符,也称为换行符,被视为一行的结尾标记(EOL)。一个回车紧接着一个换行的组合,只视作一个EOL标记来处理。EOL标记通常与任何其他空白字符相同。但是,有时需要一个EOL标记,出现在一行的开头标记之前。

PDF的四个部分

图1-2展示了PDF的四个部分:头部、预告、正文和交叉引用表。

图1-2.PDF的四个部分

头部

PDF的头从文件的0字节开始,由至少8个字节组成,后面是行尾标记。这8个字节用于明确标识这个文件是一个PDF(%PDF-),并给出文件符合的标准版本号(例如,1.4)。如果您的PDF包含实际的二进制数据(最近几乎所有的数据都包含),那么接下来将有第二行,它也以PDF注释字符%(百分比符号)开始。在第二行的%之后,至少有四个ASCII值大于127的字符。尽管任何四个(或更多)值都很好,但最常用的值是âãÏÓ(0xE2E3CFD3)

第二行通过程序来简单地计算高阶ASCII值来判断是ASCII还是二进制。包含这些值确保PDF始终被视为二进制。

预告

在PDF的头部下面,你可以找到预告。示例1-12给出了一个简单的例子。预告主要是一个字典,它包含键和值,提供文档级别的信息,这些信息是处理文档本身所必需的。

Example 1-12. 一个简单的预告

trailer
<<
 /Size 23
 /Root 5 0 R
 /ID[<E3FEB541622C4F35B45539A690880C71><E3FEB541622C4F35B45539A690880C71>]
 /Info 6 0 R
>>

 

两个最重要的键,也是仅有的两个必须要有的键是Size和Root。Size键告诉我们在预告字典前面的交叉参考表中应该找到多少条目。Root键的值为文档的目录字典,您将从这里开始查找PDF中的所有对象。

预告中的其他常见键是加密的键,其存在可以快速识别出这个PDF已被加密。ID键,它为文档提供两个唯一的ID;以及Info键,它表示提供文档级元数据的原始方法(如第12章所述,已被替换)。

正文

正文是构成实际文档本身的所有九种类型的对象都位于的位置。您将在后面的“文档结构”中看到更多关于这一点的信息,同时查看各种对象以及它们是如何被组织的。

交叉引用表

交叉参考表的概念和实现比较简单,但它是PDF的核心属性之一。此表为文件中的每个间接对象提供了相对于文件开头的二进制偏移量,允许PDF处理器在任何时间快速查找并读取任何对象。这种随机访问模型意味着可以快速打开和处理PDF,而不必将整个文档加载到内存中。此外,无论页码中的“数字跳转”有多大,页面之间的导航都是快速的。在文件末尾使用交叉引用表还提供了两个额外的好处:在一次传递中创建PDF(不进行回溯)是可能的,以及能促进对文档的增量更新的支持。(示例见后面的“增量更新”)。

交叉引用表的原始表格(PDF1.0至1.4)由一个或多个交叉引用部分组成,其中每个部分都是一系列和对象的文件偏移量、代数、以及它是否在使用中有关的条目(每个对象一行)。最常见的表类型,如图1-3所示,只有一个部分列出所有对象。

图1-3.经典交叉引用表

这种类型的交叉参考表遵循一种非常严格的格式,在这种格式中,列的位置是固定的,并且零是不可省略的。

您可能会注意到,交叉参考表每一行第二列中的数字的值总是为零,除了第一列的值为65535。该值与f一起,清楚地表明具有该ID的对象无效。由于PDF文件从来没有ID为0的对象,所以第一行始终与您在本例中看到的一样。

但是,当PDF包含增量更新时,您可能会看到类似于示例1-13中的交叉引用部分。

例1-13.更新的交叉引用部分

xref
0 1
0000000000 65535 f
4 1
0000000000 00001 f
6 2
0000014715 00000 n
0000018902 00000 n
10 1
0000019077 00000 n
trailer
<</Size 18/Root 9 0 R/Prev 14207
/ID[<86E7D6BF23F4475FB9DEED829A563FA7><507D41DDE6C24F52AC1EE1328E44ED26>]>>

 

随着PDF文档变得越来越大,很明显,拥有这种非常冗长(且不可压缩)的格式是一个需要解决的问题。因此,在PDF1.5中,引入了一种称为交叉引用流(因为数据作为标准流对象存储)的新类型的交叉引用存储系统。除了能够被压缩之外,新格式更加紧凑,支持大于10 GB的文件,同时还提供其他类型扩展的可能(尚未使用)。除了将交叉引用表改变为流之外,这个新系统还可以将间接对象的集合存储在另一种称为对象流的特殊流中。通过智能地将对象拆分到多个流中,可以优化PDF的加载时间和内存消耗。示例1-14显示了交叉引用流的样子。

例1-14.在交叉引用流中

stream
01 0E8A 0 % 对象2的条目 (0x0E8A = 3722)
02 0002 00 % 对象3的条目 (在对象流2中,索引为0)
02 0002 01 % 对象4的条目 (在对象流2中,索引为1)
02 0002 02 % . . .
02 0002 03
02 0002 04
02 0002 05
02 0002 06
02 0002 07 % 对象流10的条目 (在对象流2中,索引为7)
01 1323 0 % 对象流11的条目 (0x1323 = 4899)
endstream

增量更新

如前所述,PDF的一个关键特性就是通过使用预告和文档末尾的交叉引用表实现的,这就是增量更新的概念。由于更改的对象被写入PDF的末尾,如图1-4所示,保存修改非常快速,因为不需要读取和处理每个对象。

图1-4.包含增量更新部分的PDF布局

每个在初始数据后的交叉引用部分都通过预告字典中的Prev键返回到它之前的交叉引用(参见第16页的“拖车”),然后只列出新表中的新对象、已更改对象或已删除对象,如例1-13所示。

虽然查看器实际上不提供此功能(除了应用了后面“签名字段”中的数字签名之后),使用增量更新意味着可以跨保存边界支持多个撤消操作。然而,这也带来了危险,别人可能可以看到你之前的数据。即使您认为您从文件中删除了一些内容,但如果应用了增量更新而不是完全保存,它可能仍然存在。

在一个PDF中使用增量更新的时候,不要将经典的交叉引用与交叉引用流混为一谈是极其重要的。在原件中使用的任何类型的交叉引用都必须在更新部分中使用。如果将它们混合在一起,PDF阅读器可能会选择忽略更新。

Linearization(线性化)

正如您所看到的,在文件末尾使用交叉引用表具有各种优势。然而,也有一个很大的缺点,那就是PDF必须通过“流接口”(就像Web浏览器中的HTTP流)读取。在这种情况下,就算只想看其中的一页,一个普通的PDF也必须下载完整,这可能会造成不好的用户体验。

为了解决这个问题,PDF提供了一个叫做线性化的特性(ISO 32000-1:2008,附件F),但更多人称之为“快速网络视图”。

一个线性化文件与标准PDF文件有三种不同之处:

  1. 文件中的对象以一种特殊的方式排序,以便将特定页的所有对象组合在一起,然后按数字页码顺序组织(例如,第1页的对象,然后是第2页的对象,等等)。
  2. 在头部后面紧随着一个特殊的线性化参数字典,该字典将文件标识为线性化,并包含它所需要处理的各种信息。
  3. 在文件的开头放置部分交叉参考表和预告,以便访问根对象所需的所有对象,加上第一页要展示出来的那些对象。(通常是第一页)

当然,与标准PDF一样,对象仍然以相同的方式引用,继续通过交叉引用表对任何对象进行随机访问。如例1-15所示是线性化PDF的一个片段。

Example 1-15. 线性化PDF片段

%PDF-1.7
%%EOF
8 0 obj
<</Linearized 1/L 7546/O 10/E 4079/N 1/T 7272/H [ 456 176]>>
endobj
xref
8 8
0000000016 00000 n
0000000632 00000 n
0000000800 00000 n
0000001092 00000 n
0000001127 00000 n
0000001318 00000 n
0000003966 00000 n
0000000456 00000 n
trailer
<</Size 16/Root 9 0 R/Info 7 0 R/ID[<568899E9010A45B5A30E98293
C6DCD1D><068A37E2007240EF9D346D00AD08F696>]/Prev 7264>>
startxref
0
%%EOF
% 正文对象从这里开始...

 

混合线性化和增量更新可能会产生意想不到的结果,因为使用线性化的交叉引用表将取代只存在于文件末尾的更新版本。因此,指定用于在线使用的文件应该被完全保存,以删除更新并确保正确的线性化表。

文件结构

现在您已经了解了PDF中的各种对象以及它们是如何组合在一起形成物理文件布局/结构的,现在是时候将它们放在一起形成一个实际的文档了。

目录字典

PDF文档是对象的集合,从根对象(Root)开始(图1-5)。之所以称其为根,是因为如果您将PDF中的对象看作树(或一个有向图),这个对象位于树/图的根处。从这个对象中,您可以找到处理PDF页面及其内容所需的所有其他对象。

图1-5.PDF对象的类图结构

根始终是一个类型为目录的对象,并被称为文档的目录字典。它有两个必需的键:

  1. 类型,其值始终为名字对象目录
  2. 页,其值是对页面树的间接引用

虽然能够访问PDF的页面显然很重要,但也有二十多个可选键也可以出现(参见ISO32000-1:2008,表28)。这些代表文件级别的信息,包括:

• 基于XML的元数据(XML-based metadata)

• 打开操作 (OpenActions)

• 可填充形式 (Fillable forms)

• 可选内容(Optional content)

• 逻辑结构与标签(Logical structure and tags)

示例1-16显示了一个目录对象的示例。

Example 1-16.目录对象

<<
 /Type /Catalog
 /Pages 533 0 R
 /Metadata 537 0 R
 /PageLabels 531 0 R
 /OpenAction 540 0 R
 /AcroForm 541 0 R
 /Names 542 0 R
 /PageLayout /SinglePage
 /ViewerPreferences << /DisplayDocTitle true >>
>>

 

让我们看看一些键(以及它们的值),您可能会发现在PDF中包含这些键是很有用的,以便改进用户体验:

页面控件(PageLayout)

页面控件键用于告诉PDF查看器应该如何显示PDF页面。它的值是一个名字对象。若要一次显示它们,请使用SinglePage这个值,或者如果您希望页面全部位于一个长的连续列中,则使用OneColumn值。还可以一次为两个页面指定值(有时称为spread),具体取决于您希望奇数页在的位置:TwoPageLeft和TwoPageRight。

页模式(PageMode)

除了只显示PDF页面内容外,您可能希望用户可以立即访问PDF的一些导航元素。例如,您可能希望书签或概述可见。页模式(PageMode)键的值是一个名字对象,它明确显示了哪些额外的元素应该被显示(如果有的话),例如使用大纲(UseOutlines)、使用缩略图(UseThumbs)或使用附件(UseAttachments)。

阅读器偏好(ViewerPreferences)

与前两个示例键的值是名字对象不同,阅读器偏好(ViewerPreferences)键的值是阅读器偏好字典(见ISO 32000-1:2008,12.2)。在查看器首选项字典中可用的许多键中,最重要的一个键(如果您向文档中添加元数据,如第12章所述)在前面的示例中有显示:显示文档标题(DisplayDocTitle)。如果该值为true,则PDF查看器将指示PDF查看器在窗口的标题栏中不显示文档的文件名,如图1-6所示,而是显示其真实标题,如图1-7所示。

图1-6.显示文件名的窗口标题栏

图1-7.窗口标题栏显示文档标题

(未完待续)

10个选择题,3个编程题,还有4个Android/iOS的附加题,附加题不记得了,记录一下选择题和编程题。

一、选择题

1.有6个不同颜色的珠子,可以串成多少种不同的手环?(旋转、翻转能变成一样的认为是一种)

A.30   B.60   C.120   D.720

2、在主线程中int i = 0,再并发同时执行A和B两个函数,函数A的内容是i++;i++;函数B的内容是i+=2;则i的结果可能为?(多选)

A.0   B.1   C.2   D.3   E.4   F.5   G.6

3、bash中不是用来处理字符串的是?

A.cut   B.awk   C.sed   D.pushd

4、【1,2,3,4,5】入栈,出栈不可能为?

A.【23415】   B.【54132】   C.【23145】   D.【15432】

5、已知一颗二叉树的先序遍历序列为GDAFEMHZ,中序遍历序列为ADEFGHMZ,则后序遍历序列为?

A.ADEFGHMZ   B.DAEFHZMG   C.AEFDHZMG   D.AFEDHMZG

6、不属于操作系统进程间实现同步的方式是?

A.临界区   B.互斥量   C.进程锁   D.事件

7、在传输层中未使用TCP协议的是?

A.SMTP   B.FTP   C.TELNET   D.DNS

8、下列哪个排序方式的平均时间复杂度不是O(nlogn)?

A.选择排序   B.快速排序   C.归并排序   D.堆排序

9、下列不是死锁产生条件的是?

A.互斥   B.请求与保持   C.竞争   D.循环等待

10、TCP的可靠传输实现不包括下列哪个选项?

A.滑动窗口   B.冗余校验   C.超时重传   D.确认机制

 

二、编程题

1.定义一个数据结构Edge

class Edge{
    private int a;
    private int b;
}

表示节点a和节点b是连接在一起的。

实现如下方法,即给定一个Edge数组Edge[]graph,以及任意两个节点p和q,返回p和q是否联通。

bool isConnected(Edge[]graph , int p , int q)

2.实现一个方法:给定股票的价格序列数组prices[n],找到在该区间内股票的最大回撤值。

(找到p1,p2两个点需满足以下条件:p1在p2左边,prices[p1]>=prices[p2],prices[p1] – prices[p2]在整个区间最大)

示例:

prices[n] = {2,3,4,1,10,8,5,1,7,2}

最大回撤:prices[4] – prices[7] = 10 – 1 = 9

prices[n] = {9,8,7,6,5}

最大回撤:prices[0] – prices[4] = 9 – 5 = 4

double getMaxDrawdown(double prices[])

 

3.已知M*N矩阵,矩阵的每行从左到右递增,每列从上到下递增,给定目标值,写程序计算给出的目标值是否存在矩阵中。

bool isExist (double  matrix[][] , double value)

RT,来自网龙笔试题,判断一个整数的二进制是否是01交替。

不知道我的答案对不对。。。负数的情况略复杂。

代码如下:

bool isZeroAndOne(int num)
{
    if(num<0){
        num = -num;
        num = num ^ 2147483647;
        num++;
    }
     if(num==1||num==0)
        {
                return false;
        }
        else {
        int last = num & 1;
        while (num)
        {
                num = num >> 1;
                int cur = num & 1;
                if ((last == 1 && cur == 1) || (last == 0 && cur == 0))
                {
                        return false;
                }
                last = cur;
        }
        return true;
        }
}

 

假设有标注了 1, 2, 3, …, n 各个数字的 n 张卡片。当第 1 张卡片的 数字为 k 时,则把前 k 张卡片逆向排序,并一直重复这个操作。举个例 子,当 n = 6 时,如果由“362154”这个序列开始,则卡片的变化情况 如下。

这种情况下,卡片顺序一共变化 8 次后就无法继续变化了。

求使卡片顺序变化次数最多的 n 张卡片的顺序以及最大的变化次数。

 

1.顺序暴力递归思路:使用C++生成n位数的全排列,按照题意暴力模拟即可。

代码:

#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n);//获得数组的全排列
int fun(int a[],int deep);//求该数组翻转多少次后第一个数为1

int tempList[99];
int maxList[99];
int maxi = 0;

void all_permutation(int arr[], int n)//获得数组的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do{
      for(int i = 0;i<n;i++){
        tempList[i] = arr[i];//临时数组存储此时的全排列
      }
      int b = fun(tempList,0);//获得该排列翻转的次数,保存给b
      if(b > maxi){//如果b大于此时最大的数
        maxi = b;//最大的翻转次数更改为b
        for(int i = 0;i<n;i++){
            maxList[i] = arr[i];//存储翻转次数最多的数组更新
        }
      }
    }while(next_permutation(arr,arr+n));//获得下一个排列
}

int fun(int a[],int deep){
    if(a[0]==1){
        return deep;//如果第一个数是1的时候,返回结果
    }
   else{
    reverse(a,a+a[0]);//翻转数组的前a[0]个数
    fun(a,deep+1);//调用递归且deep+1,deep是我们的翻转次数
   }
}

int main(){
    int t;
     while(scanf("%d",&t)){
     if(t>=2 && t < 10){
     maxi = 0;
     int a[t+10];
     for(int i = 0;i<t;i++){
        a[i] = i+1;
     }
      all_permutation(a,t);
      printf("array is :");
      for(int i = 0;i<t;i++){
        printf("%d ",maxList[i]);
      }
      printf("\n");
      printf("max count = %d\n",maxi);
     }
     else{
        printf("please input number of 2~9!\n");
     }
     }
}

 

2.倒推优化递归思路:首先,数组的全排列需要第一个数是1,其次当一个数组中第i个数字是i的时候,这个数组一定有递推的上一步,否则这个数组就是最初情况。

代码:


#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n);//获得数组的全排列
void fun(int a[],int n,int deep);//递归函数

int tempList[99];//存储临时数组
int maxList[99];//存储变化次数最多的数组结果
int maxi = 0;//存储变化的最大次数

void all_permutation(int arr[], int n)//获得数组的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do
    {
        if(arr[0] == 1)
        {
            for(int i = 0; i<n; i++)
            {
                tempList[i] = arr[i];
            }
            fun(tempList,n,0);
        }
    }
    while(next_permutation(arr,arr+n));
}

void fun(int a[],int n,int deep)//递归函数
{
    if(deep > maxi){//获得最大翻转次数且存储此时的数组
        maxi = deep;
        for(int i = 0;i<n;i++){
            maxList[i] = a[i];
        }
    }
    for(int i = 1;i<n;i++){
        if(a[i]==i+1){//如果数组的第i个数等于i+1(因为数组从0开始)
            reverse(a,a+i+1);//翻转前i个数
            fun(a,n,deep+1);//开始递归,deep+1
            reverse(a,a+i+1);//翻转回去
        }
    }
}

int main()
{
    int t;
    while(scanf("%d",&t))
    {
        if(t>=2 && t < 10)
        {
            maxi = 0;
            int a[t+10];
            for(int i = 0; i<t; i++)
            {
                a[i] = i+1;
            }
            all_permutation(a,t);
            printf("array is :");
            for(int i = 0; i<t; i++)
            {
                printf("%d ",maxList[i]);
            }
            printf("\n");
            printf("max count = %d\n",maxi);
        }
        else
        {
            printf("please input number of 2~9!\n");
        }
    }
}

 

 

泉水
Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 2772(662 users) Total Accepted: 1074(597 users) Rating: Special Judge: No
Description
   Leyni是一个地址调查员,有一天在他调查的地方突然出现个泉眼。由于当地的地势不均匀,有高有低,他觉得如果这个泉眼不断的向外溶出水来,这意味着这里在不久的将来将会一个小湖。水往低处流,凡是比泉眼地势低或者等于的地方都会被水淹没,地势高的地方水不会越过。而且又因为泉水比较弱,当所有地势低的地方被淹没后,水位将不会上涨,一直定在跟泉眼一样的水位上。
由于Leyni已经调查过当地很久了,所以他手中有这里地势的详细数据。所有的地图都是一个矩形,并按照坐标系分成了一个个小方格,Leyni知道每个方格的具体高度。我们假定当水留到地图边界时,不会留出地图外,现在他想通过这些数据分析出,将来这里将会出现一个多大面积的湖。
Input
有若干组数据,每组数据的第一行有四个整数n,m,p1,p2(0<n,m,p1,p2<=1000),n和m表示当前地图的长和宽,p1和p2表示当前地图的泉眼位置,即第p1行第p2列,随后的n行中,每行有m个数据。表示这每一个对应坐标的高度。
Output
输出对应地图中会有多少个格子被水充满。
Sample Input
3 5 2 3
3 4 1 5 1
2 3 3 4 7
4 1 4 1 1
Sample Output
6

题目链接:HRBUST OJ 1143 泉水

AC代码:

#include <stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

int a[1010][1010];
bool b[1010][1010];
int sum = 0;

void search(int p1,int p2,int h,int n ,int m){
    b[p1][p2] = false;
    if(a[p1][p2]<=h){
        sum++;
    }
    if(p1+1<n && b[p1+1][p2] && a[p1+1][p2]<=h){
        search(p1+1,p2,h,n,m);
    }
    if(p1-1>=0 && b[p1-1][p2] && a[p1-1][p2]<=h){
        search(p1-1,p2,h,n,m);
    }
    if(p2-1>=0 && b[p1][p2-1] && a[p1][p2-1]<=h){
        search(p1,p2-1,h,n,m);
    }
    if(p2+1<m && b[p1][p2+1] && a[p1][p2+1]<=h){
        search(p1,p2+1,h,n,m);
    }

}



int main()
{
     int n,m,p1,p2;
    while(cin>>n>>m>>p1>>p2){
         memset(b,true,sizeof(b));

        sum = 0;
        --p1;
        --p2;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                cin>>a[i][j];
            }
        }
        int h = a[p1][p2];
        sum = 0;
        search(p1,p2,h,n,m);
        cout<<sum<<endl;
    }
}

 

如何获取所有全排列情况?STL中的代码非常精妙,利用next_permutation的返回值,判断是否全排列结束(否则将死循环)。对于给定的一个数组,打印其所有全排列只需如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

void all_permutation(int arr[], int n)//获得C++的全排列
{
    sort(arr,arr+n);    // sort arr[] in ascending order
    do{
        for(int i=0; i<n; printf("%d ",arr[i++]));
        printf("\n");
    }while(next_permutation(arr,arr+n));
}

int main(){
     int a[5]={1,2,3};
      all_permutation(a,3);
}

 

#include <iostream>
#include <string>
using namespace std;


void merge(int a[],int c[],int first,int mid,int last){
    int i = first;
    int j = mid+1;
    int k = first;
    while(i<=mid && j<=last){
        if(a[i] <= a[j]){
            c[k] = a[i];
            k++;
            i++;
        }
        else{
            c[k] = a[j];
            k++;
            j++;
        }
    }
    while(i<=mid){
        c[k]=a[i];
        k++;
        i++;
    }
    while(j<=last){
        c[k]=a[j];
        k++;
        j++;
    }
for(int i=first;i<=last;i++)a[i]=c[i];
}

void mergeSort(int a[],int c[],int first , int last){
    if(first<last){
    int mid = (first+last)/2;
    mergeSort(a,c,first,mid);
    mergeSort(a,c,mid+1,last);
    merge(a,c,first,mid,last);
}
}

int  main(){
    int a[99] = {5,4,3,2,1};
    int c[99];
    mergeSort(a,c,0,4);
    for(int i = 0 ;i<5;i++){
        cout<<a[i]<<" ";
    }
}

归并排序的思想是分而治之,将数组不断分割,最后将两部分数组合并,通过判断第一部分和第二部分数组当前元素的大小来合并,不断合并直到完成排序。

归并排序是稳定的排序方式,归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数,归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。