1、破解某论坛管理员的密码
题目描述:
　　将数字1-9填入以下九宫格，要求每行每列及每个小方格(共九个)均为1-9，不能重复出现，
管理员密码的后九位就在第五行。要求编程解出其值。
输入: 无
输出: 标准输出，输出这九个整数，每个数字占一行


2、Lagrange’s Four-Square Theorem
Input: lagrange.txt
The fact that any positive integer has a representation as the sum of at most four positive squares (i.e. squares of positive integers) is known as Lagrange’s Four-Square Theorem. The first published proof of the theorem was given by Joseph-Louis Lagrange in 1770. Your mission however is not to explain the original proof nor to discover a new proof but to show that the theorem holds for some specific numbers by counting how many such possible representations there are.
For a given positive integer n, you should report the number of all representations of n as the sum of at most four positive squares. The order of addition does not matter, e.g. you should consider 4^2 + 3^2 and 3^2 + 4^2 are the same representation.
For example, let’s check the case of 25. This integer has just three representations 1^2+2^2+2^2+4^2, 3^2 + 4^2, and 5^2. Thus you should report 3 in this case. Be careful not to count 4^2 + 3^2 and 3^2 + 4^2 separately.
Input
The input is composed of at most 255 lines, each containing a single positive integer less than 2^15, followed by a line containing a single zero. The last line is not a part of the input data.
Output
The output should be composed of lines, each containing a single integer. No other characters
should appear in the output.
The output integer corresponding to the input integer n is the number of all representations
of n as the sum of at most four positive squares.
Sample Input
1
25
2003
211
20007
0
Output for the Sample Input
1
3
48
7
738
开始时间: 2008-12-18 20:30:00
结束时间: 2008-12-26 20:30:00

第二题为选做，是我和同学以前做的 Acm 练习题，希望大家都能参与到其中来。

  最后修改于2008-12-18 20:37:00

 

E-mail: [email]liaozengxiang0827@163.com[/email]

A response test.

 

我必须过了20号才能做题目，20号要考英语！期待好的答案

 

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

int count=0;

void LFST(int temp,int lim,int n)
{
    for(int i=(int)sqrt(temp/n);i<=(int)sqrt(temp)&&i<=lim;i++)
    {
        if(i*i==temp)
            count++;
        else if(i*i<temp)
        {
            if(n-1!=0)
                LFST(temp-i*i,i,n-1);
        }
    }
}

void main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int temp;
    fin>>temp;
    while(temp!=0)
    {    
        LFST(temp,sqrt(temp)+1,4);
        fout<<count<<endl;
        count=0;
        fin>>temp;
    }    
}

 

第一题的图看不到,只能做第二题...

 

0.0

 

jp b dkcjo

 

 

参与，，呵呵，大家一起进步！！
第一题：
// 2008.12.23 v1.0  write by qingfengliandie
#include <stdio.h>
int main()
{
    int a[9][9] = {{0,0,3,8,1,0,0,0,9},
                   {5,0,0,4,0,0,0,8,0},
                   {0,6,0,9,0,0,1,0,0},
                   {0,0,8,0,3,0,0,0,6},
                   {0,0,0,0,0,0,0,0,0},
                   {9,0,0,6,0,0,5,0,0},
                   {0,0,6,0,0,9,0,1,0},
                   {0,1,0,0,0,5,0,0,4},
                   {2,0,0,0,4,8,7,0,0}
                   };
    int m=0;
    int n=0;
    if(sub1(a,m,n)==0){
    printf("OK!\n");
    }
    return 0;
}
int sub1(int b[9][9], int m, int n) {
    int re,k;
    if(b[m][n] > 0){
       if(n==8){
        re=sub1(b,m+1,0);
       }
       else{
           re=sub1(b,m,n+1);
       }
       if(re==1){
           return 1;
       }
       else{
           return 0;
       }
    }
    else{
      for(k=1;k<10;k++){
          b[m][n]=k;
          if (sub2(b,m,n)==0 ){
              if(m==8 && n == 8){
              sub3(b);
              return 0;
            }
            if(n==8){
               re=sub1(b,m+1,0);
            }
            else{
                  re=sub1(b,m,n+1);
            }
            if(re==0){
                  return 0;
            }
            else{
                  if(k==9){
                        b[m][n]=0;
                  return 1;}
            }
        }
        else{
            if(k==9){
            b[m][n]=0;
            return 1;}
        }
      }
    }
 }
int sub3(int b[9][9]){
  int i,j;                
    for (i = 0 ;i < 9;i++){
           if(i==6){
          printf("the password is:\n");
          for(j = 0;j < 9;j++){
          printf(" %d ",b[i][j]);
             }
          printf("\n");
       }
    }
  return     0;    
}     
int sub2(int b[9][9], int m, int n) {
 int i,j;
 int s[9];
 int k=0;
 int z = (int)m/3;
 int x = (int)n/3;    
  for ( i = 0;i<9;i++){
      for ( j = i+1;j<9;j++){    
      if(b[m][i]!=0 && b[m][i]==b[m][j]){return 1;}
      if(b[i][n]!=0 && b[i][n]==b[j][n]){return 1;}
      }
  }
  for ( i = 0;i<3;i++){
      for ( j = 0;j<3;j++){
     s[k++] = b[z*3+i][x*3+j];
      }
  }
 for ( i = 0;i<9;i++){
      for ( j = i+1;j<9;j++){
      if(s[i]!=0 && s[i]==s[j]){return 1;}
      }
  }
 return 0;
}
     

  最后修改于2008-12-23 23:33:00

第一题

 

1,居然看不见那数独图片.....应该大概思路是预处理+回溯+剪枝吧...有个问题是不知道图给的数独解是否唯一
2.简单枚举了....

 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define max 32768
int cal_sqare(int n)
{
    int i;
    int j;
    int k;
    int l;
    int sum = 0;
    int count = 0;

    int s = (int)sqrt(n);

    for (i = 1; i <= s; i++)
    {
        sum += i * i;

        if(n == sum)
        {
            count++;
            sum = 0;
            break;
        }

        for (j = i; j <= s; j++)
        {
            sum += j * j;

            if (n == sum)
            {
                count++;
                sum -= j * j;
                break;
            }

            if (sum > n)
            {
                sum -= j * j;
                break;
            }

            for (k = j; k <= s; k++)
            {
                sum += k * k;

                if (n == sum)
                {
                    count++;
                    sum -= k * k;
                    break;
                }

                if (sum > n)
                {
                    sum -= k * k;
                    break;
                }

                for (l = k; l <= s; l++)
                {
                    sum += l * l;

                    if(n == sum)
                    {
                        count++;
                        sum -= l * l;
                        break;
                    }

                    if (sum > n)
                    {
                        sum -= l * l;
                        break;
                    }

                    sum -= l * l;
                }
                sum -= k * k;
            }
            sum -= j * j;
        }
        sum -= i * i;
    }

    return count;
}

int main()
{
    int i = 0;
    int j;
    int c;
    int input[255];
    char line[255];

    FILE *file;

    if((file = fopen("input.txt", "r")) == NULL)
    {
        printf("open file error!\n");
        return -1;
    }

    do
    {
        fgets(line, 255, file);
        input[i++] = atoi(line);
    }while((input[i - 1] != 0) && (i < 255));

    for (j = 0; j < (i - 1); j++)
    {
        if (input[j] <= max)
        {
            c = cal_sqare(input[j]);
            printf("%d\n", c);
        }
        else
        {
            printf("line%d's value in the file is larger than 2^15\n", j);
        }
    }
    return 0;
}

 

/***************************************************************************************
  运行环境：
   Microsoft Visual C++ 6.0

  程序设计思想:
    获得信息:
      rowInfo: 第i行可以放的数(如: 5) , 则 rowInfo[i][5-1] = 1
      rowSepColInfo: 第i行不可以放的数(如: 5)的列号 , 则 rowSepColInfo[i][5-1] = 列号
      colInfo, colSepRowInfo 与此类似,
    数据处理
      1. 每三行一组,在这三行中找出在同一列中，只有一个位置可以放的数，即满足
       （rowInfo[i][j] + rowInfo[i][j+1] + rowInfo[i][j+2] == 1）, 找出该元素的
        行号和列号。然后，如果在这一行的三列中，只有一个位置放数，则将该元素放到
        对应的坐标上，修改rowInfo 和 colInfo 信息。
      2. 用同样方法处理，每三列一组
      3. 对每一行剩余可以放的元素（如：5），检测从第0列到N-1列可以放的元素，如果只有一列
         可以放该元素，则在对应位置放上该元素（5），然后修改rowInfo 和 colInfo 信息
      4. 用同样的方法处理每一列
****************************************************************************************/

#include <iostream>
#include <fstream>

using namespace std;

#define N 9

int nineSquare[N][N]={{0, 0, 3, 8, 1, 0, 0, 0, 9},
                      {5, 0, 0, 4, 0, 0, 0, 8, 0},    
                      {0, 6, 0, 9, 0, 0, 1, 0, 0},
                      {0, 0, 8, 0, 3, 0, 0, 0, 6},
                      {0, 0, 0, 0, 0, 0, 0, 0, 0},
                      {9, 0, 0, 6, 0, 0, 5, 0, 0},
                      {0, 0, 6, 0, 0, 9, 0, 1, 0},
                      {0, 1, 0, 0, 0, 5, 0, 0, 4},
                      {2, 0, 0, 0, 4, 8, 7, 0, 0},
};

int rowInfo[N][N] = {0}; // 存储每一行可以放的信息
int rowSpeColInfo[N][N] = {0}; // 存储不能放数据的元素所在 N 行的列号
int colInfo[N][N] = {0}; // 存储每一列可以放的信息
int colSpeRowInfo[N][N] = {0}; // 存储不能放数据的元素所在 N 列的行号

void getInfo()
{  // 得到每行每列可以存放的信息, 1表示当前位置可以放数字

    // 初始化 rowInfo, colInfo 数组, 所有位置都能放数据
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            rowInfo[i][j] = 1;
            colInfo[i][j] = 1;
        }
    }

    for( i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            if(nineSquare[i][j] != 0)
            {
                rowInfo[i][ nineSquare[i][j]-1 ] = 0; // 当前行 对应nineSquare[i][j]-1 的位置 不能放了
                rowSpeColInfo[i][nineSquare[i][j]-1 ] = j; // 记录当前行不能放数据的 位置（i, j）
                colInfo[ nineSquare[i][j]-1 ][j] = 0; // 当前列 对应nineSquare[i][j]-1 的位置 不能放了
                colSpeRowInfo[ nineSquare[i][j]-1 ][j] = i; // 记录当前列不能放数据的 位置（i, j）
            }
        }
    }
}

  最后修改于2008-12-26 19:29:00

// 由于空格太多，请用Vc里自动排版功能Alt+F8
bool process()
{ // 对数据数组进行处理, 如果当前有数据处理，返回true, 否则，返回false

int x, y;
int value;

bool flag = false;

getInfo();

int i , j;

for(i = 0; i < 3; ++i)
{
for( j = 0; j < N; ++j)
{
int startPos = 0; // 

// 找到每三行中一行必须存在的数
if(rowInfo[i*3][j] + rowInfo[i*3+1][j] + rowInfo[i*3+2][j] == 1)
{  //  找到三列中惟一存在的数

y = j;
value = j + 1;

if(rowInfo[i*3][j] == 1)
{
x = i*3;
}
else
startPos += rowSpeColInfo[i*3][j] / 3;

if(rowInfo[i*3+1][j] == 1)
{
x = i*3+1;
}
else
startPos += rowSpeColInfo[i*3 + 1][j] / 3;

if(rowInfo[i*3+2][j] == 1)
{
x = i*3+2;
}
else
startPos += rowSpeColInfo[i*3 + 2][j] / 3;

//cout << "by x:      x = " << x << "   y = " << y << "  value = " << value << endl;

startPos = (3 - startPos)*3;
int goodX, goodY;
int count = 0;
for(int m = startPos; m < startPos+3; ++m)
{
if(nineSquare[x][m] == 0)  // ( x, m ) 可以放元素
{
if(colInfo[j][m] == 1)  // m 列中 可以存放 value 为 j 的元素
{
goodX = x;
goodY = m;
count ++; // 计数 可以替换的位置
}
}
}

if( count == 1) // 只有一个位置被替换
{
nineSquare[goodX][goodY] = j+1;

// 修改rowInfo colInfo信息
rowInfo[goodX][j] = 0;
colInfo[j][goodY] = 0;

flag = true; // 进行了数据处理
}
}
}
}

// 对每三列的数据处理
for(j = 0; j < 3; ++j)
{
for( i = 0; i < N; ++i)
{
// 找到每三列中一行必须存在的数
if(colInfo[i][j*3] + colInfo[i][j*3+1] + colInfo[i][j*3+2] == 1)
{
int startPos = 0; // 

x = i;
value = i + 1;
if(colInfo[i][j*3] == 1)
{
y = j*3;
}
else
startPos += colSpeRowInfo[i][j*3] / 3;

if(colInfo[i][j*3+1] == 1)
{
y = j*3+1;
}
else
startPos += colSpeRowInfo[j][i*3 + 1] / 3;

if(colInfo[i][j*3+2] == 1)
{
y = j*3+2;
}
else
startPos += colSpeRowInfo[j][i*3 + 2] / 3;

//cout << "by y:      x = " << x << "   y = " << y << "  value = " << value << endl;

startPos = (3 - startPos)*3;
int goodX, goodY;
int count = 0;
for(int m = startPos; m < startPos+3; ++m)
{
if(nineSquare[m][y] == 0)  // ( x, m ) 可以放元素
{
if(rowInfo[m][j] == 1)  // m 列中 可以存放 value 为 j 的元素
{
goodX = m;
goodY = y;
count ++; // 计数 可以替换的位置
}
}
}

if( count == 1) // 只有一个位置被替换
{
nineSquare[goodX][goodY] = j+1;

// 修改rowInfo colInfo信息
rowInfo[goodX][j] = 0;
colInfo[j][goodY] = 0;

flag = true; // 进行了数据处理
}
}
}
}


// 对每一行
for(i = 0; i < N; ++i)
{
for(j = 0; j < N; ++j)
{
if( rowInfo[i][j] == 1) // 第 i 行可以放的元素 j+1
{
int count = 0; // 记录可以拥有该元素的列的次数

int goodX, goodY;

goodX = i;
for(int k = 0; k < N; ++k)
{
if( colInfo[j][k] == 1 && nineSquare[i][k] == 0) // 第k列可以拥有该元素
{
goodY = k;
count ++;
}
}

if(count == 1) // 只有一列可以放这个元素
{
nineSquare[goodX][goodY] = j+1;

// 修改rowInfo colInfo信息
rowInfo[goodX][j] = 0;
colInfo[j][goodY] = 0;

flag = true; // 修改了数据
}
}
}
}

// 对每一列
for(j = 0; j < N; ++j)
{
for(i = 0; i < N; ++i)
{
if( colInfo[i][j] == 1) // 第 j 列可以放的元素 i+1
{
int count = 0; // 记录可以拥有该元素的列的次数

int goodX, goodY;

goodY = j ;
for(int k = 0; k < N; ++k)
{
if( rowInfo[k][i] == 1 && nineSquare[k][j] == 0 ) // 第k行可以拥有该元素, 并且(k, j) 没有元素
{
goodX = k;
count ++;
}
}

if(count == 1) // 只有一列可以放这个元素
{
nineSquare[goodX][goodY] = i+1;

// 修改rowInfo colInfo信息
rowInfo[goodX][j] = 0;
colInfo[j][goodY] = 0;

flag = true; // 修改了数据
}
}
}
}

return flag;
}

 

void display()
{ // 显示九宫表的信息

    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            cout << nineSquare[i][j] << '\t';
        }
        cout << endl;
    }
}

int main()
{
    bool flag = true;

    while( flag ) // 调用处理函数，直到不能再放入元素为止。
        flag = process();    

    cout << "九宫表是：" << endl;
    display();

    cout << "\n管理员密码后九位是: " << endl;
    for(int i = 0; i < N; ++i)
    {
        cout << nineSquare[4][i] << '\t';
    }
    cout << endl;

    return 0;
}

 

// 第二题，时间来不及了，就测了25 的结果正确， 也把它交上


#include <iostream>
#include <math.h>

using namespace std;

int main()
{
int m = 25;

int n = sqrt(m);

int count = 0;

for( int a = n; a > 0; --a )
{
int b = a;
while( a*a + b*b > m && b > 0)
b--;

if( a*a + b*b == m)
{
count++;
cout << "a : " << a << "  b : " << b << endl;
b--;
}

if(b > 0)
{
// 第三个数
int c = b;
while( a*a + b*b + c*c > m && c > 0)
c--;

if( a*a + b*b + c*c == m)
{
count++;
cout << "a : " << a << "  b : " << b << endl;
c--;
}

if( c > 0 )
{
int d = c;
while( a*a + b*b + c*c + d*d > m && d > 0)
d--;

if( a*a + b*b + c*c + d*d == m)
{
cout << "a : " << a << "  b : " << b << "   d : " << d << endl;
count++;
c--;
}
}

}
}

cout << count << endl;
return 0;
}

 

比赛时间到, 结贴!