@ZHANGQIANYI2020
HNUCM-OJ 习题6-6 杨辉三角，小白鼠，放苹果，数字交换，棋盘覆盖问题，整数划分问题之备忘录法
问题 A: 习题6-6 杨辉三角
（时间限制: 1 Sec 内存限制: 12 MB）
题目描述：
按要求输出如下格式的杨辉三角
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
最多输出10层。
输入：
输入只包含一个正整数n，表示将要输出的杨辉三角的层数。
输出：
对应于该输入，请输出相应层数的杨辉三角，每一层的整数之间用一个空格隔开。
样例输入：
5
样例输出：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
参考答案：
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
int n=sc.nextInt();
int a[][]=new int[n+1][n+1];
for(int i=1;i<=n;i++) {
for(int j=1;j<=i;j++) {
if(i==j) {
a[i][j]=1;
}
else if(i==1||j==1) {
a[i][j]=1;
}else {
a[i][j]=a[i-1][j-1]+a[i-1][j];
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=i;j++) {
System.out.print(a[i][j]+" ");
}
System.out.println();
}
}
}
}
问题 B: 小白鼠
（时间限制: 1 Sec 内存限制: 128 MB）
题目描述：
N只小白鼠(1 <= N <= 100)，每只鼠头上戴着一顶有颜色的帽子。
现在称出每只白鼠的重量，要求按照白鼠重量从大到小的顺序输出它们头上帽子的颜色。
帽子的颜色用“red”，“blue”等字符串来表示。
不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。
输入：
多案例输入，每个案例的输入第一行为一个整数N，表示小白鼠的数目。
下面有N行，每行是一只白鼠的信息。第一个为不大于100的正整数，表示白鼠的重量；
第二个为字符串，表示白鼠的帽子颜色，字符串长度不超过10个字符。
注意：白鼠的重量各不相同。
输出：
每个案例按照白鼠的重量从大到小的顺序输出白鼠的帽子颜色。
样例输入：
3
30 red
50 blue
40 green
样例输出：
blue
green
red
参考答案：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
int n=sc.nextInt();
int a[]=new int[n];
String b[]=new String[n];
for(int i=0;i<n;i++) {
a[i]=sc.nextInt();
b[i]=sc.next();
}
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
if(a[i]<a[j]) {
int s=a[i];
a[i]=a[j];
a[j]=s;
String color=b[i];
b[i]=b[j];
b[j]=color;
}
}
}
for(int i=0;i<n;i++) {
System.out.println(b[i]);
}
}
}
}
问题 C: 放苹果
（时间限制: 1 Sec 内存限制: 128 MB）
题目描述：
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
（用K表示）5，1，1和1，5，1 是同一种分法。
输入：
每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出：
对输入的每组数据M和N，用一行输出相应的K。
样例输入：
7 3
样例输出：
8
参考答案：
import java.util.Scanner;
public class Main{
public static int fangpingguo(int m,int n){
if(m==0||n==1){
return 1;
}
if(n>m){
return fangpingguo(m,m);
}
return fangpingguo(m,n-1)+fangpingguo(m-n,n);
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int m=sc.nextInt();
int n=sc.nextInt();
int s=0;
s=fangpingguo(m,n);
System.out.println(s);
}
}
}
问题 D: 数字交换
（时间限制: 1 Sec 内存限制: 128MB）
题目描述：
输入一个数n，然后输入n个数值各不相同，调换数组中最大和最小的两个数，然后输出。
输入：
测试数据有多组，输入n(1<=n<=20)，接着输入n个数。
输出：
对于每组输入,输出交换后的结果。
样例输入：
2
1 3
样例输出：
3 1
参考答案：
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
int n=sc.nextInt();
int M=0,N=0;
int a[]=new int[n];
int Min=0,Max=0,MinIndex=0,MaxIndex=0;
int temp;
for(int i=0;i<n;i++) {
a[i]=sc.nextInt();
}
for(int i=0;i<n;i++) {
if(i==0){
Min=a[i];
Max=a[i];
MinIndex=i;
MaxIndex=i;
}
if(Max<a[i]){
Max=a[i];
MaxIndex=i;
}
if(Min>a[i]){
Min=a[i];
MinIndex=i;
}
}
temp=a[MinIndex];
a[MinIndex]=a[MaxIndex];
a[MaxIndex]=temp;
for(int i=0;i<n;i++){
System.out.print(a[i]);
if(i !=n-1){
System.out.print(" ");
}
}
System.out.println();
}
}
}
问题 E: 棋盘覆盖问题
（时间限制: 1 Sec 内存限制: 256MB）
题目描述：
在一个n×n (n = 2k)个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
输入：
多组测试用例，每组测试用例包括两部分，
第一部分为方格的宽度n，
第二部分则为方格，特殊方格为-1，其他方格为0。
输出：
输出覆盖后的方案
样例输入：
4
-1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
样例输出：
-1 2 4 4
2 2 1 4
3 1 1 5
3 3 5 5
参考答案：
import java.util.Scanner;
public class Main {
static int title=1;
public static void qipanfugai(int a[][],int tr,int tc,int dr,int dc,int size){
if(size==1)return;
int t=title++;
int s=size/2;
if(dr<tr+s&&dc<tc+s){
qipanfugai(a,tr,tc,dr,dc,s);
}else{
a[tr+s-1][tc+s-1]=t;
qipanfugai(a,tr,tc,tr+s-1,tc+s-1,s);
}
if(dr>=tr+s&&dc<tc+s){
qipanfugai(a,tr+s,tc,dr,dc,s);
}else{
a[tr+s][tc+s-1]=t;
qipanfugai(a,tr+s,tc,tr+s,tc+s-1,s);
}
if(dr<tr+s&&dc>=tc+s){
qipanfugai(a,tr,tc+s,dr,dc,s);
}else{
a[tr+s-1][tc+s]=t;
qipanfugai(a,tr,tc+s,tr+s-1,tc+s,s);
}
if(dr>=tr+s&&dc>=tc+s){
qipanfugai(a,tr+s,tc+s,dr,dc,s);
}else{
a[tr+s][tc+s]=t;
qipanfugai(a,tr+s,tc+s,tr+s,tc+s,s);
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int x = 0,y = 0;
int n=sc.nextInt();
int a[][]=new int[n][n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
a[i][j]=sc.nextInt();
if(a[i][j]==-1){
x=i;
y=j;
}
}
qipanfugai(a,0,0,x,y,n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print(a[i][j]+" ");
}
System.out.println();
}
title=1;
}
}
}
问题 F: 整数划分问题之备忘录法
（时间限制: 1 Sec 内存限制: 128MB）
题目描述：
使用备忘录法编写一个程序，求一个正整数n的所有划分个数。
例如，输入3，输出3；输入4，输出5。
输入：
多组输入，每一组是一个正整数n。
输出：
输出划分数。
样例输入：
3
4
样例输出：
3
5
参考答案：
import java.util.Scanner;
public class Main {
static int a[][]=new int[100][100];
static int n;
public static int beiwanglu(int n,int m) {
if((n<1)||(m<1))
return 0;
if((n==1)||(m==1))
return 1;
if(n<m)
return beiwanglu(n,n);
if(n==m){
if (a[n-1][n-2]==0) {
a[n-1][n-2] = beiwanglu(n,n-1);
}
return 1 + a[n-1][n-2];
}
if (n>m) {
if (a[n-m-1][m-1]==0) {
a[n-m-1][m-1]=beiwanglu(n-m,m);
}
if (a[n-1][m-2]==0) {
a[n-1][m-2] = beiwanglu(n,m-1);
}
return a[n-1][m-2] + a[n-m-1][m-1];
}else{
return 0;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
n=sc.nextInt();
System.out.println(beiwanglu(n,n));
}
}
}