小宁博客 - 算法
type: channel
link: http://www.sunxiaoning.com/tag/suanfa/
items: 1011 A+B 和 C (15分)Python参考答案
items: 1009 说反话 (20分)Python参考答案
items: 1007 数组元素循环右移问题 (20分)Python参考答案
items: 1007 素数对猜想 (20 分)Python参考答案
items: PAT乙级1005 继续(3n+1)猜想 (25 分)Python参考答案
items: 相似度算法之欧几里得距离
items: PAT乙级1003. 我要通过！(20)java,Python参考答案
items: PAT乙级1002写出这个数 (20)java,Python参考答案
items: 选择排序和冒泡排序

1011 A+B 和 C (15分)Python参考答案
type: item
date: 2020-01-16T17:20:32+08:00
description: 给定区间 [−2^31,2^​31] 内的 3 个整数 A、B 和 C，请判断 A+B 是否大于 C。输入格式：输入第 1 行给出正整数 T (≤10)，是测试用例的个数。随后给出 T 组测试用例，每组占一行，顺序给出 A、B 和 C。整数间以空格分隔。输出格式：对每组测试用例，在一行中输出 Case #X: true 如果 A+B>C，否则输出 Case #X: false，其中 X 是测试用例的编号（从 1 开始）。输入样例：41 2 32 3 42147483647 0 21474836460 -2147483648 -2147483647输出样例：Case #1: falseCase #2: trueCase #3: trueCase #4: false解析：代码：#!/usr/bin/python a = input() i = 0 result=[] while i<a: s = raw_input() s_list = s.split(" ") if int(s_list[0]) + int(s_list[1])>int(s_list[2]): result.append('true') else: result.append('false') i+=1 for index,item in enumerate(result): print("Case #%d: %s" %(index+1,item))

1009 说反话 (20分)Python参考答案
type: item
date: 2020-01-16T11:08:00+08:00
description: 给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。输入格式：测试输入包含一个测试用例，在一行内给出总长度不超过 80 的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用 1 个空格分开，输入保证句子末尾没有多余的空格。输出格式：每个测试用例的输出占一行，输出倒序后的句子。输入样例：Hello World Here I Come输出样例：Come I Here World Hello解析：首先我们输入的死一个字符串，单词与单词之间是用空格进行的的划分，我们可以根据空格划分为列表，然后把列表进行倒叙。列表倒叙我们采用的事切片的操作实现代码：#!/usr/bin/python s = raw_input() s_list = s.split(" ") print(" ".join(s_list[-1:-len(s_list)-1:-1]))

1007 数组元素循环右移问题 (20分)Python参考答案
type: item
date: 2020-01-15T18:23:05+08:00
description: 1007 数组元素循环右移问题 (20分)Python参考答案输入格式:每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。输出格式:在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。输入样例:6 21 2 3 4 5 6输出样例:5 6 1 2 3 4答案解析：我们首先分析下这个题，输入了n代表了我们将要操控的列表的长度，所以我们要限制我们的列表长度不能超过n。移动m位，那么我们可以采用python里面的切片，这时候，小编就写完了，也提交了，结果没有满分，后来分析了下，m有可能大于n，切片的时候，以m为中间，那么有问题，就改造了下，我们一起来看下代码吧。#!/usr/bin/python s = raw_input() s_list = s.split(" ") n = int(s_list[0]) m = int(s_list[1]) s = raw_input() s_list = s.split(" ") if m>n: m -= n a = [] for i in s_list[0: n]: a.append(str(i)) print(" ".join(a[-m:]+a[:-m]))

1007 素数对猜想 (20 分)Python参考答案
type: item
date: 2019-09-30T07:46:00+08:00
description: 输入格式:输入在一行给出正整数N。输出格式:在一行中输出不超过N的满足猜想的素数对的个数。输入样例:20输出样例:4分析在分析之前，小编先说下python的运行效率是真的不是很高，小编的算法优化了好几次才可以，最后的一个测试用例总是超时，20分的算法题只能拿18分，有强迫症的小编好难受，终于功夫不负有心人，完美解决。大体的思路就是先判断素数，然后判断两个相邻的素数是否相差为2.细节：偶数肯定不是素数。最小的素数对是3，5求素数的时候先开方，具体理由自己思考。代码18分的代码（经历就不说了）#!/usr/bin/python import math n = input() t = 1 jishu = 0 for num in range(2, n+1): chushu = math.sqrt(num) f = True for number in range(2, int(chushu)+1): if num%number==0: f = False break if f: if(num-t==2): jishu+=1 t = num print jishu20分的#!/usr/bin/python import math n = input() def issushu(num): chushu = math.sqrt(num) for number in range(3, int(chushu)+1, 2): if num%number==0: return False return True t = True jishu = 0 for number in range(3, n-1, 2): t2=issushu(number+2) if t and t2: jishu+=1 t = t2 print jishu

PAT乙级1005 继续(3n+1)猜想 (25 分)Python参考答案
type: item
date: 2019-09-25T08:02:00+08:00
description: 原题卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n 为“关键数”，如果 n 不能被数列中的其他数字所覆盖。现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。输入格式：每个测试输入包含 1 个测试用例，第 1 行给出一个正整数 K (<100)，第 2 行给出 K 个互不相同的待验证的正整数 n (1<n≤100)的值，数字间用空格隔开。输出格式：每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用 1 个空格隔开，但一行中最后一个数字后没有空格。输入样例：63 5 6 7 8 11输出样例：7 6解题思路遍历所有输入的数，求出每个数的覆盖数，去重之后保存在一个列表中。遍历覆盖数，输入的数如果在覆盖数里面则删除，剩下的都是关键数了。对关键数进行排序，输出。Python2示例代码#!/usr/bin/python n = input() s = raw_input() s_list = s.split(" ") s_list = [int(item) for item in s_list] n_cover_list = [] for n in s_list: while n!=1: if n%2==0: n/=2 else: n=((3*n)+1)/2 if n not in n_cover_list: n_cover_list.append(n) for item in n_cover_list: if item in s_list: s_list.remove(item) s_str = '' s_list = sorted(s_list, reverse=True) for index in range(len(s_list)): s_str = s_str+str(s_list[index]) if index==0 else s_str+' '+str(s_list[index]) print(s_str)

相似度算法之欧几里得距离
type: item
date: 2019-08-10T15:56:00+08:00
description: 欧几里得距离算法是经过人们一致评价的物品为坐标轴，然后将参与评价的人绘制到图上，并考察他们彼此之间距离的远近，如图：注：图片来源于《集体智慧编程》上图是在二维空间中6位用户对Snakes 和 Dupree 这两Item评价的直观体现就其意义而言，欧几里得距离越小，两个用户相似度就越大，欧氏距离越大，两个用户相似度就越小。在日常使用中，一般习惯于将相似度与1类比，相似度在数值上反映为0<=Similarity(X,y)<=1，越接近1，相似度越高；等于1时则表示两人具有一样的偏好。那么我们在使用欧几里得距离时，可以通过 1/（1+Distance(X,Y)）来贯彻上一理念，加一是为了避免遇到被零整除的情况。欧几里德距离是指多维空间两点间的距离，这是一种用直尺测量出来的距离。如果将两个点分别标记为$(p_1,p_2,p_3....p_n)$和$(q_1,q_2,q_3.....q_n)$,则欧几里德距离的计算公式为：$$\sqrt{(p_1-q_1)^2+(p_2-q_2)^2...+(p_n-q_n)^2} = \sqrt{\sum_{i=1}^{n}(p_i-q_i)^2}$$计算图python代码的实现#返回一个有关person1与person2的基于距离的相似度评价 def sim_distance(prefs,person1,persion2): #得到shared_items的列表 si = {} for item in prefs[person1]: if item in prefs[persion2]: si[item] = 1 #如果两者没有共同之处，则返回0 if len(si) == 0: return 0 #计算所有差值的平方和 sum_of_squares = sum([pow(prefs[person1][item]-prefs[persion2][item],2) for item in prefs[person1] if item in prefs[persion2]]) #返回（距离+1）的倒数 return 1/(1+sqrt(sum_of_squares))

PAT乙级1003. 我要通过！(20)java,Python参考答案
type: item
date: 2017-10-17T10:22:00+08:00
description: 题目“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。得到“答案正确”的条件是：字符串中必须仅有P, A, T这三种字符，不可以包含其它字符；任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a, b, c 均或者是空字符串，或者是仅由字母 A 组成的字符串。现在就请你为PAT写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。输入格式： 每个测试输入包含1个测试用例。第1行给出一个自然数n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过100，且不包含空格。输出格式：每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出YES，否则输出NO。输入样例：8PATPAATAAPATAAAAPAATAAAAxPATxPTWhateverAPAAATAA输出样例：YESYESYESYESNONONONO代码示例及解析import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main{ static Scanner sc; public static void main(String[] args) { sc = new Scanner(System.in); int a = sc.nextInt(); if(a<10)//由题意可知，第1行给出一个自然数n (<10)，是需要检测的字符串个数。 arr(a); } //定义一个函数，实现判断 public static void arr(int f) { List<String> al = new ArrayList<String>(); int i=1; while(i<=f) { String s= sc.next(); al.add(s); i++; } //输出集合中的所有字符串 for (String string : al) { int a=0,p=0,t=0,p1=0,t1=0;//定义一些变量，用来判别字符个数 char [] s = string.toCharArray(); //字符串转换成字符数组 //遍历每个字符数组，判断输出什么 for (char str : s) { /** * 确定只有PAT三个字符，否则直接输出“NO”，同时确定3个位置A的个数 * 有题可知P前面吗A的个数乘以PT之间A的个数等于T后面A的个数 * p代表P前面Ade个数，t代表PT之间A的个数，a代表T后面A的个数 * 所以t*p==a * p1,t2用来判断P和T的个数是不是1 */ if(str=='A'||str=='P'||str=='T') { if('A'==str) { a++; }else if('P'==str) { p1++; p=a; a=0; }else if(('T'==str)&&(p1==1)) {//P必须在T的前面 t1++; t=a; a=0; } }else { break; } } if((t*p==a)&&(a!=0||p!=0||t!=0)&&(p1==1&&t1==1)) { System.out.println("YES"); }else { System.out.println("NO"); } } } } Python实现#!/usr/bin/python n = input() i = 0 str_list = [] while i<n: i = i+1 s = raw_input() str_list.append(s) for item in str_list: p = 0 a = 0 t = 0 aa = 0 ap = 0 at = 0 if 'P' not in item or 'A' not in item or 'T' not in item: print('NO') continue for i in item: if i not in 'PAT': p=a=t=0 break if i == 'A' : a=a+1 elif i == 'P': p=p+1 elif i == 'T': t=t+1 if i == 'A' and p==0 and t==0: aa=aa+1 elif i=='A' and p==1 and t==0: ap=ap+1 elif i=='A' and t==1: a…

PAT乙级1002写出这个数 (20)java,Python参考答案
type: item
date: 2017-10-12T09:33:00+08:00
description: 题目：读入一个自然数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。这里保证n小于10100。输出格式：在一行内输出n的各位数字之和的每一位，拼音数字间有1 空格，但一行中最后一个拼音数字后没有空格。输入样例：1234567890987654321123456789输出样例：yi san wujava参考答案: import java.awt.List; import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { int sum = 0; Scanner sc = new Scanner(System.in); String s = sc.next(); //把输入的字符串转换成字符数组 char ch[] = s.toCharArray(); //遍历数组 for (char c : ch) { //求和：把字符数组中的字符先转换成字符串，在将字符串转成int类型 sum += Integer.valueOf(String.valueOf(c)); } //把和转换成字符串，载转换成字符数组 char ch1[] = String.valueOf(sum).toCharArray(); //定义一节集合，对应和中每个数字以及要输出的字符串 Map<Character, String> m = new HashMap<>(); m.put('0', "ling"); m.put('1', "yi"); m.put('2', "er"); m.put('3', "san"); m.put('4', "si"); m.put('5', "wu"); m.put('6', "liu"); m.put('7', "qi"); m.put('8', "ba"); m.put('9', "jiu"); //定义一个字符串，方便组拼输出结果（字符串） String sums=" "; //遍历由和转换的字符串数组 for (char c : ch1) { //组拼字符串 sums = sums+m.get(c)+" "; } //输出结果，去掉头和尾的空格 System.out.print(sums.trim()); } }python2参考答案#!/usr/bin/python n = input() l = ['ling', 'yi', 'er', 'san', 'si', 'wu', 'liu', 'qi', 'ba', 'jiu', 'shi'] s = str(n) sum = 0 for i in s: sum += int(i) sum_str = str(sum) sum_sum = '' for index, sum_i in enumerate(sum_str): sum_sum = sum_sum+l[int(sum_i)] if index == 0 else sum_sum+' '+l[int(sum_i)] print sum_sum

选择排序和冒泡排序
type: item
date: 2017-08-25T16:08:00+08:00
description: 选择排序工作原理选择排序的的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。算法实现（所用语言为java）public static void selectSort(int [] arr) { for(int i = 0;i<arr.length-1;i++){ for(int x = i;x<arr.length;x++) { if(arr[i]>arr[x]) { int temp = arr[i]; arr[i] = arr[x]; arr[x] = temp; } } } }例子讲解数组：[12,11,34,65,334,23,55]第一次排序：[12,11,34,65,334,23,55]第二次排序：[11,12,34,65,334,23,55]第三次排序：[11,12,34,65,334,23,55]第四次排序：[11,12,23,65,334,34,55]第五次排序：[11,12,23,34,334,65,55]第六次排序：[11,12,23,34,55,334,65]第七次排序：[11,12,23,34,55,65,334]冒泡排序工作原理比较相邻的元素，如果第一个比第二个大（或者第一个比第二个小），就交换他们两个，对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大（或最小）的数。针对所有的元素重复以上的步骤，除了最后一个，持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。代码实现(java语言）public static void buttleSort(int [] arr) { for(int i = 0;i<arr.length-1;i++) { for(int x=0;x<arr.length-1-i;x++) { if(arr[x]>arr[x+1]) { int temp = arr[x]; arr[x] = arr[x+1]; arr[x+1] = temp; } } } }-例子讲解数组：[12,11,34,65,334,23,55]第一次排序：[12,11,34,65,334,23,55]第一次排序：[11,12,34,65,23,55,334]第一次排序：[11,12,34,23,55,65,334]第一次排序：[11,12,23,34,55,65,334]第一次排序：[11,12,23,34,55,65,334]第一次排序：[11,12,23,34,55,65,334]第一次排序：[11,12,23,34,55,65,334]写的相对来说比较简单了，算法实现的代码不是唯一的，所以小编在这里仅提供了相对简单的实现代码，感兴趣的小伙伴，如果不明白，可以给我留言，我一定会回复的哦。附：完整代码public class Sort { public static void main(String[] args) { int [] arr = {12,11,34,65,334,23,55}; System.out.print("排序前的结果："); printArray(arr); selectSort(arr); System.out.print("选择排序结果："); printArray(arr); buttleSort(arr); System.out.print("冒泡排序结果："); printArray(arr); } //选择排序 public static void selectSort(int [] arr) { for(int i = 0;i<arr.length-1;i++){ for(int x = i;x<arr.length;x++) { if(arr[i]>arr[x]) { swap(arr,i,x); } } } } //冒泡排序 public static void buttleSort(int [] arr) { for(int i = 0;i<arr.length-1;i++) { for(int x=0;x<arr.length-1-i;x++) { if(arr[x]>arr[x+1]) { swap(arr,x,x+1); } } } } //交换函数 public static void swap(int [] arr,int x,int y) { int temp = arr[x]; arr[x]=arr[y]; arr[y]=temp; } //遍历函数 public static void printArray(int [] arr) { for(int i=0;i<arr.length;i++) { if(i!=a…