《算法分析与设计四》

问题A： 请编写一个程序，输出0到n(包括n)中数字2出现了几次。

import java.util.Scanner; public class MainA { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int sum = 0; int n = scanner.nextInt(); for(int i=0;i<=n;i++){ String s = String.valueOf(i); for(int j=0;j<s.length();j++){ if(Integer.parseInt( s.substring(j, j+1))==2){ sum++; } } } System.out.println(sum); } } }

解题思路：将数字一个个分开，再看2出现几次

这题主要应用了几个函数 1.String.valueOf(int i) : 将 int 变量 i 转换成字符串 。

2.substring():返回子字符串。 public String substring(int beginIndex) 或 public String substring(int beginIndex, int endIndex)

beginIndex – 起始索引（包括）, 索引从 0 开始。

endIndex – 结束索引（不包括）。

3.Integer.parseInt(String s):将字符串转换成整形。

问题B 请实现一个算法，确定一个字符串的所有字符是否全都不同。 给定一个字符串，请返回一个True代表所有字符全都不同，False代表存在相同的字符。

import java.util.Scanner; public class MainB { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ String str = scanner.next(); char s[] = str.toCharArray(); outer: if(str.length()<3000){ for(int i=0;i<s.length;i++){ for(int j=0;j<s.length;j++){ if(i!=j){ if(s[i]==s[j]){ System.out.println("False"); break outer; } } } } System.out.println("True"); } } } }

解题思路：将字符串转换成字符数组，再将下标不同的数组元素进行比较

应用函数：toCharArray()：将字符串转换成字符数组

问题C Kimi有两盒（A、B）乒乓球，有红双喜的、有亚力亚的……现在他需要判别A盒是否包含了B盒中所有的种类，并且每种球的数量不少于B盒中的数量，该怎么办呢？

import java.util.Scanner; public class MainC { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int flag=1; char[] A = scanner.next().toCharArray(); char[] B = scanner.next().toCharArray(); int s[] = new int[26]; for(int i=0;i<A.length;i++){ s[A[i]-'A']++; } for(int j=0;j<B.length;j++){ s[B[j]-'A']--; } for(int i=0;i<s.length;i++){ if(s[i]<0){ flag=0; break; } } if(flag==0){ System.out.println("No"); }else{ System.out.println("Yes"); } } } }

解题思路：将字符串转换成字符数组，将字符数组元素-'A’作为整型数组下标，将字符数组元素个数作为整型数组元素。如果flag为负数则输出No

问题D 1, 2, 3…9 这九个数字组成一个分数，其值恰好为1/3，要求每个数字出现且只能出现一次，如何组合？编写程序输出所有的组合。

public class MainD { private static int[] arr = new int[2]; private static int t = 0; public static void main(String[] args) { int a[]={1,2,3,4,5,6,7,8,9}; fun(a,0); if(arr[0]>arr[1]){ swap(0,1,arr); } for(int i=0;i<arr.length;i++){ System.out.println(arr[i]+"/"+arr[i]*3); } } private static void fun(int[] a,int k ) { ArrayList list = new ArrayList(); if(k==8){ int x=a[0]*1000+a[1]*100+a[2]*10+a[3]*1; int y=a[4]*10000+a[5]*1000+a[6]*100+a[7]*10+a[8]; if(x*3==y){ arr[t]=x; t++; } }else{ for(int i=k;i<a.length;i++){ swap(i,k,a); fun(a,k+1); swap(i,k,a); } } } public static void swap(int m,int n,int a[]){ int t = a[m]; a[m] = a[n]; a[n] = t; } }

解题思路：与“字母全排列问题相似”，关键在于将A/B=1/3转换成A*3=B，和按照分子大小从小到大输出：将符合要求的分子存储在数组中（分母为分子的3倍，所以存储分子即可），再进行排序输出。

问题E 使用递归编写一个程序，求一个正整数n的所有划分个数。 例如，输入3，输出3；输入4，输出5。

import java.util.Scanner; public class MainE { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int x = scanner.nextInt(); System.out.println(fun(x,x)); } } private static int fun(int m,int n) { if((m<1) || (n<1)){ return 0; } if((m==1) || (n==1)){ return 1; } if(m==n){ return fun(m,m-1)+1; } if(m<n){ return fun(m,m); } return fun(m-n,n)+fun(m,n-1); } }

问题F 请编写一个程序，输入包含n（n<=10000）个整数的数列S以及包含q个(q<=500)不重复整数的数列T，输出既包含于T也包含于S的整数的个数C。S、T中的元素均大于0且小于109，T的元素不重复。

import java.util.Scanner; public class MainF { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int n,q,x = 0; n=scanner.nextInt(); int s[] =new int[n]; for(int i=0;i<n;i++){ s[i]=scanner.nextInt(); } q=scanner.nextInt(); int T[] =new int[q]; for(int j=0;j<q;j++){ T[j]=scanner.nextInt(); } for(int i1=0;i1<q;i1++){ out: for(int j1=0;j1<n;j1++){ if(T[i1]==s[j1]){ x++; break out; } } } System.out.println(x); } } }

问题G 使用递归算法，实现二分搜索。

import java.util.Scanner; public class MainG { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int n = scanner.nextInt(); int s[] = new int[n]; for(int i=0;i<n;i++){ s[i] = scanner.nextInt(); } int x = scanner.nextInt(); System.out.println(fun(s,0,n-1,x)); } } private static int fun(int[] s, int low, int high, int x) { if(low>high) return -1; int mid = (low+high)/2; if(s[mid]==x){ return mid+1; }else if(s[mid]<x){ return fun(s,mid+1,high,x); }else{ return fun(s,low,mid-1,x); } } }

问题H 使用非递归算法，实现二分搜索。 输入输出同问题G

import java.util.Scanner; public class MainH { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int low=0,high,mid; int n = scanner.nextInt(); high = n-1; int s[] = new int[n]; for(int i=0;i<n;i++){ s[i] = scanner.nextInt(); } int x = scanner.nextInt(); while(true){ if(high>=low){ mid = (low+high)/2; if(s[mid]==x){ System.out.println(mid+1);break; } if(s[mid]<x){ low=mid+1; } if(s[mid]>x){ high = mid-1; } }else{ System.out.println(-1);break; } } } } }

问题I 一次大型派对的最后节目是选出一位幸运人士，该人士将获得派对组织者准备的一个钻石戒指。 而选择幸运人士的办法是让所有人员一字排列，然后从左至右点数，凡是奇数号的全部剔除。 对于剩下的人员，又从左至右点数，逢奇数号就剔除。 如此不断递归下去，直到只剩下一个人为止，此人即为幸运之人。 请设计一个递归算法计算幸运之人所在的位置。

import java.util.Scanner; public class MainI { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int n =scanner.nextInt(); System.out.println(fun(n)); } } private static int fun(int n) { if(n==1){ return 1; }else{ return fun(n/2)*2; } } }

题解思路：符合规律：f(n)=f(n/2)*2

问题J 设a[0:n-1]是已排好序的数组。请改写二分搜索算法，使得当待搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素的位置j；当待搜索元素x在数组中时，返回的i和j相同，均为x在数组中的位置

//非递归 import java.util.Scanner; public class MainJ { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int n = scanner.nextInt(); int a[] = new int[n]; for(int i=0;i<n;i++){ a[i] = scanner.nextInt(); } int x = scanner.nextInt(); int low =0; int high = n-1; while(true){ if(low>high){ System.out.println(low+" "+(low+1));break; }else{ int mid = (low+high)/2; int i; if(a[mid]==x){ System.out.println((mid+1)+" "+(mid+1));break; } if(a[mid]>x){ high = mid-1; } if(a[mid]<x){ low = mid+1; } } } } } }

问题k 经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩，当然这个传说并不可信，如今汉诺塔更多的是作为一个玩具存在。Gardon就收到了一个汉诺塔玩具作为生日礼物。   Gardon是个怕麻烦的人（恩，就是爱偷懒的人），很显然将64个圆盘逐一搬动直到所有的盘子都到达第三个柱子上很困难，所以Gardon决定作个小弊，他又找来了一根一模一样的柱子，通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是：当Gardon在一次游戏中使用了N个盘子时，他需要多少次移动才能把他们都移到第三个柱子上？很显然，在没有第四个柱子时，问题的解是2^N-1，但现在有了这个柱子的帮助，又该是多少呢？

import java.util.Scanner; public class MainJ { public static void main(String[] args) { int x[] = new int[65]; x[0]=0; int a=1,b=a,k=1; for(int i=1;i<x.length;i++){ x[i]=(x[i-1]+k); b--; if(b==0){ a++; b=a; k*=2; } } Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int n = scanner.nextInt(); if(n>0&&n<=64){ System.out.println(x[n]); } } } }

问题L 用1,2,…,n表示n个盘子，称为1号盘，2号盘,…。号数大盘子就大。经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘。我们知道最少需要移动2^64-1次.在移动过程中发现，有的圆盘移动次数多，有的少 。 告之盘子总数和盘号，计算该盘子的移动次数.

import java.util.Scanner; public class MainL { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); for(int i=0;i<n;i++){ int N = scanner.nextInt(); int k = scanner.nextInt(); long s = 1; for(int j=0;j<(N-k);j++){ s=s*2; } System.out.println(s); } } }

解题思路：符合规律： 2的N-k次方 参考博客：汉诺塔问题合集