算法练习（1）
题集
1.乌托邦数
| private static void analyse(int inNum) { BigInteger result = new BigInteger("1"); BigInteger MUL = new BigInteger("2"); BigInteger ADD = new BigInteger("1"); for(int i=0;i<inNum;i++) { if(i%2==0) { result = result.multiply(MUL); }else { result = result.add(ADD);}} System.out.println(result.toString());} |
2.最小公倍数
| public class addNums03 { private static BigInteger result = new BigInteger("1"); public static void main(String[] args) { Scanner scan = new Scanner(System.in); int inNum = scan.nextInt(); analyse(inNum); scan.close(); System.out.println(result); } private static void analyse(int inNum) { for(int i=2;i<=inNum;i++) { BigInteger nextNum = new BigInteger(String.valueOf(i)); BigInteger gcdNum = new BigInteger(String.valueOf(gcd(result,nextNum))); result = result.multiply(nextNum).divide(gcdNum);//a,b的最小公倍数等于a*b/a,b的最大公因数 }
}
private static BigInteger gcd(BigInteger result2, BigInteger nextNum) { if(result2.compareTo(nextNum)<0) { BigInteger temp; temp = result2; result2 = nextNum; nextNum = temp; } BigInteger temp; while(nextNum.intValue() !=0 ){ temp = result2.mod(nextNum);//辗转相除法求最小公倍数，除数做被除数，余数做除数 result2 = nextNum; nextNum = temp; } return result2; }}
|
3.有理数循环节
| public class addNums03 { public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); String in = scan.next(); int Divisor = Integer.parseInt(in.split(",")[0]); int Divide = Integer.parseInt(in.split(",")[1]); analyse(Divisor,Divide); scan.close(); }
private static String analyse(int divisor, int divide) { int []result = new int[1000]; int firstNum,temp; firstNum = temp = divisor; while(firstNum/10!=0) { firstNum/=10; } boolean flag = false; int i; for(i=0;;i++) {
result[i] = divisor / divide; divisor = divisor % divide; if(divisor == 0) break; if(divisor == firstNum&&i!=0) { flag = true; break; } divisor *=10; } if(flag == true) { System.out.print(result[0]+".["); for(int j=1;j<=i;j++) { System.out.print(result[j]); } System.out.print("]"); }else { System.out.print((double)temp/divide); } return null; } } |
或者：
或
| private static void analyse(int divisor, int divide) { BigDecimal decimal1; BigDecimal decimal2; BigDecimal decimal3; decimal1 = new BigDecimal(divisor); decimal2 = new BigDecimal(divide); decimal3 = decimal1.divide(decimal2,25,BigDecimal.ROUND_HALF_UP); String result = decimal3.toString(); int pos; if(result.charAt(0)=='0') { pos = 2; }else { pos = 0; } int end = result.substring(pos+1).indexOf(result.charAt(pos)); if(end!=-1) { System.out.println(result.substring(0,pos+end+1)); }else { System.out.println(divisor/divide); }
} |
4.饮料换购
| private static void analyse(int num) { int temp = num; int sum = 0; while(num>2) { sum += num/3; num = num/3 + num%3; } System.out.println(sum + temp);} |
5.螺旋矩阵
| private static int [][] buildMatrix(int row, int column) { int r,c,count; r = c = count = 0; int [][] nums = new int [row][column]; while(nums[r][c]==0&&r<row&&c<column) { while(r<row&&c<column&&nums[r][c]==0) { nums[r][c] = ++count; c++; }//右 c--;r++; while(r<row&&c<column&&nums[r][c]==0) { nums[r][c] = ++count; r++; }//下 r--;c--; while(r<row&&-1<c&&c<column&&nums[r][c]==0) { nums[r][c] = ++count; c--; }//左 c++;r--; while(r<row&&c<column&&nums[r][c]==0) { nums[r][c] = ++count; r--; }//上 r++;c++; } return nums; } |
6.排列序数
| public static final int []WEIGHT = {0,1,2,6,24,120}; //表示每个位可能的字母数，其实用阶乘算一下就行，4！=24，5！=120… public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); String s = scan.nextLine(); int []nu = buildNu(s.toCharArray()); int sum = 0; int len = nu.length; for(int j=0;j<len;j++) { sum += nu[j]*WEIGHT[len-j-1]; } System.out.println(sum); scan.close(); } private static int [] buildNu(char []str) { int len = str.length; int []nu = new int[len]; for(int i=0;i<len;i++) {//这里直接找右边比自己小的字母个数即可,不用图片的两步 for(int j=i+1;j<len;j++) { if(str[i]>str[j]) nu[i]++; } } return nu;}}
|
7.长草
| public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); int row = scan.nextInt(); int column = scan.nextInt(); char space[][] = new char[row][column]; for(int i=0;i<row;i++) { String str = scan.next(); space[i] = str.toCharArray(); } int month = scan.nextInt(); analyse(space,month); scan.close(); }
private static void analyse(char[][] space, int month) { int col =space[0].length; int row =space.length; char[][] temp = new char[row][col]; for(int i=0;i<row;i++) { temp [i] = space[i].clone();}
while(month-->0) { for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { if(temp[i][j]=='g') { if(j>0) { space[i][j-1]='g'; }if(j<col-1) { space[i][j+1]='g'; }if(i>0) { space[i-1][j]='g'; }if(i<row-1) { space[i+1][j]='g';}}}} for(int i=0;i<row;i++) { temp [i] = space[i].clone();}}
for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { System.out.print(space[i][j]);} System.out.println();}} |
8.约瑟夫环
借用公式：f(N,M)=(f(N−1,M)+M)%n
参考：https://blog.csdn.net/u011500062/article/details/72855826
| public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int m = scan.nextInt(); int pos = 0; for(int i=2;i<=n;i++) { pos = (pos + m)%i; } System.out.println(pos+1); scan.close(); } |
9.摆花
分析题目可得：
用f(i,j)表示i种花放在j个盆里的摆法，则有
f(i,j)=f(i-1,j-0)+f(i-1,j-1)+…+f(i-1,j-a[i])
| public static int []aNums = new int [102]; public static final int MOD = 1000007; public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int m = scan.nextInt(); for(int i=0;i<n;i++) { aNums[i] = scan.nextInt(); aNums[i+1] = -1; } int sum = cal(n,m); System.out.println(sum); scan.close(); }
private static int cal(int i, int j) { int sum = 0;//2 4 if(i==1&&j==0||i==1&&aNums[i-1]<j) return 0; if(i==1&&j!=0) return 1; for(int k=0;k<=aNums[i-1];) { sum = (sum + cal(i-1,j-k)) % MOD; k++;} return sum%MOD; } |
参考代码：
| #include <iostream> #include<cstdio> using namespace std; int f[101][101], n, m, a[101]; int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) cin>>a[i]; f[0][0]=1; for(int i=1;i<=n;i++) //n 种数花 for(int j=0;j<=m;j++) //m 个盆 for(int k=0;k<=a[i];k++) //a[i]第 i种花的数量 {if(j<k) break; //k是当前第 i种花取的数量 ，当 盆数多于第 i 种花数 f[i][j]=(f[i][j]+f[i-1][j-k])%1000007;} cout<<f[n][m];} |