求解2道编程入门必做题(用Java)

Question

题目如下:
1.在一个４＊４的小方格（如图所示）中放置８个＊号，使得每行每列放且
 仅放两个＊号。          ┌─┬─┬─┬─┐
          │＊│＊│  │  │
          ├─┼─┼─┼─┤
          │＊│  │＊│  │
          ├─┼─┼─┼─┤
          │  │＊│  │＊│
          ├─┼─┼─┼─┤
          │  │  │＊│＊│
          └─┴─┴─┴─┘ 求出所有的基本解。
2. 已知 N 个正整数满足 K1+K2+...+Kn=M。求一组最佳的分解，使得
 K1*K2*....*Kn 为最大。
   例如：N=2时，给定 K1+K2=6,当 K1=3,K2=3 时，K1*K2=9 为最大

Answer 1

/*. 已知 N 个正整数满足 K1+K2+...+Kn=M。求一组最佳的分解，使得
 K1*K2*....*Kn 为最大。
*/
package com.itfirefly.test;public class FindMaxKey {
public static void main(String[] args){
//System.out.println("helo!");
FindMaxKey.keyMax=new Key();
FindMaxKey.keyMax.key=new int[3];
FindMaxKey.keys=new int[3];
FindMaxKey.find(3, 3, 10);
System.out.println("Max="+FindMaxKey.keyMax.max);
System.out.println("the key");
for(int i=0;i<3;i++){
System.out.print(FindMaxKey.keyMax.key[i]+"  ");
}
}

private static void find(int maxN,int n,int cunt){
if(n>1&&cunt>0){
for(int i=1;i<cunt;i++){
 FindMaxKey.keys[n-1]=i;
 find(maxN,n-1,cunt-i);
}
}else{
if(cunt>0){
FindMaxKey.keys[0]=cunt;
int cunts=1;
for(int i=0; i<maxN;i++){
cunts*=FindMaxKey.keys[i];
}
if(cunts>keyMax.max){
keyMax.max=cunts;
int i;
for(i=0; i<maxN;i++){
keyMax.key[i]=keys[i];
}
//keyMax.key[i]=cunt;
}
}
}
}

public static int[] keys;
private static Key keyMax=new Key() ;
}class Key{
public int max=0;
public int []key;
public Key(){

}
}

Answer 2

第一题设置个计数器，当每行达到2个*的时候continue 在设置个列行数数组 每当该列加入*时响应的列数据+1当列数据达到2时跳过该行。

Answer 3

1.回溯法，需要注意的是由于方格是轴且中心对称的，
只需要考虑左上四分方一方格的回溯或深搜就行了
2.完全是数学
根据基本不等式的结论
y=x1*x2*x3.....Xn 且x1+x2+x3+...+Xn=常数P,则Y的最大值为((x1+x2+x3+.....+Xn)/n)^n 
当这些个数相等的时候，它们的乘积最大
不过既然都需要正整数
那么就调整下，
让这些数差的绝对值最大为1就是符合要求的结果

Answer 4

不好意思。看差了，没看清还要列。那这样的话其实可以搞个2维的boolean数组。

Answer 5

第一题不说第二题，
  int[] k =new[n];
  i= M/n;
  j =M%n; for(int f=0;f<j;f++){
   k[f] = i+1;
}
for(int f=j;f<n;f++){
 k[f] = i;}具体的判断不写了 个人感觉这样思路效率高点

Answer 6

一定要注意判断M<n的情况

Answer 7

#include <iostream>
using namespace std;
const int N = 4;
int selected[N][N];
int colCoins[N]; //记录每列当前的硬币数量
int gCount = 0;
void Print()
{
cout << "第" << gCount << "组" << endl;
for (int i = 0;i<N;i++)
{
for (int j = 0;j<N;j++)
{
cout << selected[i][j] << " ";
}
cout << endl;
}
cout << endl << endl;
gCount++;}
void Initialize()
{
for (int i = 0;i<N;i++)
{
for (int j = 0;j<N;j++)
{
selected[i][j] = 0;
}
colCoins[i] = 0;
}}void Go(int row)
{
if (row == N) //得到了一个可行解，输出可行解
{
Print();
return;
}
for (int i = 0;i<N;i++)
{
for (int j = i+1;j<N;j++)
{
if (colCoins[i] < 2 && colCoins[j] < 2) //这两个位置可以放置硬币
{
colCoins[i]++;colCoins[j]++;
selected[row][i] = selected[row][j] = 1;
Go(row + 1);
colCoins[i]--;colCoins[j]--;               //回溯
selected[row][i] = selected[row][j] = 0;
}
}
}
}
void main()
{
// Initialize();
Go(0);
cout << "共有" << gCount << "组解"<<endl;}