回 帖 发 新 帖 刷新版面

主题:入门必做的题

1.  给定等式  A B C D E     其中每个字母代表一个数字,且不同数字对应不
                    D F G     同字母。编程求出这些数字并且打出这个数字的
             +      D F G     算术计算竖式。

             ───────

                X Y Z D E



  2. A、B、C、D、E五名学生有可能参加计算机竞赛,根据下列条件判断哪些
  人参加了竞赛:

   (1)A参加时,B也参加;

   (2)B和C只有一个人参加;

   (3)C和D或者都参加,或者都不参加;

   (4)D和E中至少有一个人参加;

   (5)如果E参加,那么A和D也都参加。



  3. 打印一个 N*N 的方阵,N为每边           N=15  打印出下面图形
 字符的个数(3<N<20), 要求最               TTTTTTTTTTTTTTT
 外一层为"T", 第二层为"J", 从第三层               TJJJJJJJJJJJJJT
 起每层依次打印数字 1,2,3,...                     TJ11111111111JT
 (右图以N为15为例)                           TJ12222222221JT
                                                  TJ12333333321JT
                                                  TJ12344444321JT
                                                  TJ12345554321JT
                                                  TJ12345654321JT
                                                  TJ12345554321JT
                                                  TJ12344444321JT
                                                  TJ12333333321JT
                                                  TJ12222222221JT
                                                  TJ11111111111JT
                                                  TJJJJJJJJJJJJJT
                                                  TTTTTTTTTTTTTTT



  4. 在N行N列的数阵中, 数K(1〈=K〈=N)在每行和每列中出现且仅
  出现一次,这样的数阵叫N阶拉丁方阵。例如下图就是一个五阶拉丁方阵。
  编一程序,从键盘输入N值后,打印出所有不同的N阶拉丁方阵,并统计个数。

        1  2  3  4  5
        2  3  4  5  1
        3  4  5  1  2
        4  5  1  2  3
        5  1  2  3  4


  5. 输入一个十进数,将其转换成 N 进制数(0<N<=16)。

回复列表 (共635个回复)

171 楼

to machh
可能是中英文输入法的问题,你自己输入一下看行不行
帖上来的一般不会有什么问题的

172 楼

55楼的还真是牛人啊!那么多的循环我以为要很多时间,想不到运行起来比想象的快的多了!

173 楼

第一题太夸张了。这是个虫食算式,一般的做法时间复杂度很高。下面给个官方的解法:
虫食算
【解题报告】

给出一个N进制的虫食算式,相同的字母代表相同的数字,不同的字母代表不同的数字。要求求出满足这个算式的唯一一组解,也就是字母和数字的一一对应关系.
解决方案1: 
要求一一对应的关系,就可以枚举这些一一对应的关系,找出符合的一项。这样,关系总数有O(N!)个,最坏情况下必须枚举所有的关系,并且加以判断,复杂度高达O(N*N!)!
解决方案2:
     大体上,从算式最后一位开始模拟运算情况,当可递推时递推,不可递推则枚举。
对于一竖列,先处理两个加数,当遇到的字母的值不确定时,则枚举当前位(注意与前面的情况判重);否则不作为。后处理和,当遇到的字母的值不确定时,可从加数部分确定的值来确定(注意与前面的情况判重和进位);否则看加数部分确定的值是否能得到和部分(注意进位)。引出矛盾就回溯。
如题目的样例:
5
ABCED
BDACE
EBBAA
它最后一位的情况是(D+E) mod N=A, 对于最后一位只要枚举D,E的情况;A 则可以由D,E的值递推而来。对于倒2位, (D+C+最后一位进位) mod N=A ;D的值可以用前面的结果;枚举C;判断A是否为(D+C+最后一位进位) mod N……
     虽然复杂度还是O(N!),但这种方法限制很多(相当于剪枝)。
解决方案3: 
观察题目的条件已经限制得很苛刻:N个变量,每个至少出现一次;而且正好一共有N位的算式。这样就构成了解方程的动机。这N个变量的对应N个未知量,有N位的算式对应N个方程;N个未知量,N个方程,正好可以得到唯一解。这里要注意,对解的要求很严格:必须是0至N-1的每个整数都正好出现一次。
     但对每位式子的进位关系并不清楚,而进位关系正好影响了方程的常数项。枚举每位是否进位。用时 (因为首位不可能进位,无须枚举)。然后,用高斯消元法来解方程。可以在枚举之前先解出方程,枚举的时候再把参数带入。带入求解的复杂度是 。
解决方案4:
     在解决方案3的基础上,我们可以对进位的枚举剪枝。观察这个竖列:A+B=C,若无进位则有A<=C且B<=C; 若有进位则有A=>C且B>=C.
     若能推导出A<=B 且B>=A (A,B为任何不相等字母),则当前的枚举不可行。可用递归枚举,从后向前枚举,处理一个竖列时则加上2个不等式,看是否矛盾。数据结构用邻接矩阵。(规定A<=B,再有向图中有边<A,B>)。
例子若加进不等式A>=B ,要加入所有x(x>=A) >=y(B>=y),枚举x,y用O(n^2)得时间。再判断是否有x<=y 且x>=y.
对比这题,解法3无效,而且也不知道这个官方算法的代码实现。GCC大大,这个第一题都这么夸张了怎么循序渐进呀?

174 楼

19. (背包问题) 有 N 件物品 d1,......dN,每件物品重量为 W1,..., WN
 (Wi > 0), 每件物品价值为 V1,......VN (Vi>0)。用这N件物品的某个子集
 填空背包,使得所取物品的总重量<=TOTAL,并设法使得背包中物品的价值尽可
 能高。

19.解答:
#include<stdio.h>

#define MAX_N 10
#define MAX_WEIGHT 20
#define MAX_VALUE 20

void bag(const int Weight[], const int Value[], const int n, const int TotalWeight)
{
    int ValueReached[MAX_VALUE*MAX_N+1] = {0};
    int WeightUsed[MAX_VALUE*MAX_N+1];
    int LastUseIndex[MAX_VALUE*MAX_N+1];
    int i,j;
    const int INF = 10000000;

    for(i=0; i<=MAX_VALUE*MAX_N; ++i)
        WeightUsed[i] = INF;

    ValueReached[0] = 1;    // 记录价值为i是否可达到
    WeightUsed[0] = 0;        // 记录达到价值i时使用的重量
    LastUseIndex[0] = -1;    // 记录达到价值i所使用物品的最后一个的下标

    for(i=0; i<n; ++i)
    {
        int w = Weight[i];
        int v = Value[i];
        for(j=MAX_VALUE*MAX_N-v; j>=0; --j)
        {
            if( !ValueReached[j] )
                continue;
            if( WeightUsed[j]+w > TotalWeight )
                continue;
            if( (!ValueReached[j+v]) || (WeightUsed[j+v]>WeightUsed[j]+w) )
            {
                ValueReached[j+v] = 1;
                LastUseIndex[j+v] = i;
                WeightUsed[j+v] = WeightUsed[j] + w;
            }
        }
    }

    for(i=MAX_VALUE*MAX_N; /*i>=0*/; --i)
        if(ValueReached[i])
            break;
    printf("可装入物品总价值为%d\n", i);

    printf("装入了以下物品:\n");
    // 注意:输出的顺序是“反”的,如果要“正”的,需另外处理
    j=LastUseIndex[i];
    while( j != -1 )
    {
        printf("第%d件\t", j+1);
        i -= Value[j];
        j = LastUseIndex[i];
    }
    printf("\n");
}

int main(void)
{
    int i;
    int TotalWeight,n;
    int w[MAX_N], v[MAX_N];
    printf("输入背包可承受的最大重量:\n");
    scanf("%d", &TotalWeight);
    printf("输入物品的件数:\n");
    scanf("%d", &n);
    for(i=0; i<n; ++i)
    {
        printf("输入第%d件物品的重量:\n", i+1);
        scanf("%d", w+i);
        printf("输入第%d件物品的价值:\n", i+1);
        scanf("%d", v+i);
    }

    bag(w, v, n, TotalWeight);

    return 0;
}

175 楼

20. (N皇后) 在国际象棋的棋盘上放置N个皇后,使其不能互相攻击,即任意
 两个皇后不能处在棋盘的同一行,同一列,同一斜线上,试问共有多少种摆法?

20.解答:
#include<stdio.h>

#define MAX 20

static int N;
static int Count;
static int map[MAX];
static int used[MAX];

void Solve(int start)
{
    int i,j;
    if( start == N )
    {
        ++Count;
        printf("Answer #%d:\n", Count);
        for(i=0; i<N; ++i)
        {
            for(j=0; j<map[i]; ++j)
                printf("□");
            printf("■");
            for(j=map[i]+1; j<N; ++j)
                printf("□");
            printf("\n");
        }
        printf("\n");
        return;
    }
    for(i=0; i<N; ++i)
    {
        if( used[i] )
            continue;
        for(j=0; j<start; ++j)
            if( map[j]+j==i+start || map[j]-j==i-start )
                break;
        if( j<start )
            continue;
        used[i] = 1;
        map[start] = i;
        Solve(start+1);
        used[i] = 0;
    }
}

int main(void)
{
    int i;
    scanf("%d", &N);
    Count = 0;
    for(i=0; i<N; ++i)
        used[i] = 0;
    Solve(0);
    return 0;
}

176 楼

21. 请设计一个程序,由计算机把1...8的八个自然数填入图中,使得横、
 竖、对角任何两个相邻的小方格中的两个数是不连续的。(下图右侧的 4 个图
 为禁止的情形).

            ┌─┐          ┌─┐               ┌─┐
            │  │          │4│               │8│
        ┌─┼─┼─┐      └─┼─┐       ┌─┼─┘
        │  │  │  │          │5│       │7│
        ├─┼─┼─┤          └─┘       └─┘
        │  │  │  │      ┌─┐
        └─┼─┼─┘      │6│           ┌─┬─┐
            │  │          ├─┤           │1│2│
            └─┘          │7│           └─┴─┘
                            └─┘
21.解答:
思路分析:把方块按下图所示编号。
    ┌─┐
    │0│
┌─┼─┼─┐
│1│2│3│
├─┼─┼─┤
│4│5│6│
└─┼─┼─┘
    │7│
    └─┘
和0相邻的有:1,2,3
和1相邻的有:0,2,4,5
和2相邻的有:0,1,3,4,5,6
和3相邻的有:0,2,5,6
和4相邻的有:1,2,5,7
和5相邻的有:1,2,3,4,6,7
和6相邻的有:2,3,5,7
和7相邻的有:4,5,6
由此得到一个二维数组:(-1表示结束)
static int Neighbor[8][7] =
{
{1,2,3,-1},
{0,2,4,5,-1},
{0,1,3,4,5,6,-1},
{0,2,5,6,-1},
{1,2,5,7,-1},
{1,2,3,4,6,7,-1},
{2,3,5,7,-1},
{4,5,6,-1}
};
如果按照0,1,2,3,4,5,6,7的顺序放数字,则先放的不需要考虑是否和后放的冲突,只需要后放的去考虑是否与先放的冲突。
所以原数组可减掉一部分,变为:
static int Neighbor[8][7] =
{
{-1},
{0,-1},
{0,1,-1},
{0,2,-1},
{1,2,-1},
{1,2,3,4,-1},
{2,3,5,-1},
{4,5,6,-1}
};


利用递归可写出程序如下:
#include<stdio.h>

static int Neighbor[8][7] =
{
    {-1},
    {0,-1},
    {0,1,-1},
    {0,2,-1},
    {1,2,-1},
    {1,2,3,4,-1},
    {2,3,5,-1},
    {4,5,6,-1}
};
static int map[8];
static int used[8];
static int count;

void Print()
{
    printf("Answer #%d:\n", count);
    printf(
            "    ┌─┐\n"
            "    │%2d│\n"
            "┌─┼─┼─┐\n"
            "│%2d│%2d│%2d│\n"
            "├─┼─┼─┤\n"
            "│%2d│%2d│%2d│\n"
            "└─┼─┼─┘\n"
            "    │%2d│\n"
            "    └─┘\n",
            map[0], map[1], map[2], map[3],
            map[4], map[5], map[6], map[7]);
    printf("\n");
}

void Solve(int start)
{
    int i,j;
    if( start == 8 )
    {
        ++count;
        Print();
        return;
    }
    for(i=0; i<8; ++i)
    {
        if( used[i] )
            continue;
        j = 0;
        while( Neighbor[start][j] != -1 )
        {
            int tmp = map[Neighbor[start][j]] - 1;
            if( tmp==i+1 || tmp==i-1 )
                break;
            ++j;
        }
        if( Neighbor[start][j] != -1 )
            continue;
        used[i] = 1;
        map[start] = i+1;
        Solve(start+1);
        used[i] = 0;
    }
}

int main(void)
{
    count = 0;
    Solve(0);
    return 0;
}


运行结果:
Answer #1:
    ┌─┐
    │ 2│
┌─┼─┼─┐
│ 5│ 8│ 6│
├─┼─┼─┤
│ 3│ 1│ 4│
└─┼─┼─┘
    │ 7│
    └─┘

Answer #2:
    ┌─┐
    │ 2│
┌─┼─┼─┐
│ 6│ 8│ 5│
├─┼─┼─┤
│ 4│ 1│ 3│
└─┼─┼─┘
    │ 7│
    └─┘

Answer #3:
    ┌─┐
    │ 7│
┌─┼─┼─┐
│ 3│ 1│ 4│
├─┼─┼─┤
│ 5│ 8│ 6│
└─┼─┼─┘
    │ 2│
    └─┘

Answer #4:
    ┌─┐
    │ 7│
┌─┼─┼─┐
│ 4│ 1│ 3│
├─┼─┼─┤
│ 6│ 8│ 5│
└─┼─┼─┘
    │ 2│
    └─┘

177 楼

好题

178 楼

好难呀!
对于我来说!!

179 楼

14题
   main()
 {
  int n,i,j,temp;
  int *a;

  scanf("  %d",&n);
  a=(int *)malloc(sizeof(int)*n*2);

  for(i=0;i<n;i++)
    *(a+i)=0;
  for(;i<2*n;i++)
    *(a+i)=1;

 if(n%2==0) 
   for(i=1,j=n;i<n;i+=2,j+=2)
     {
      temp=*(a+i);
      *(a+i)=*(a+j);
      *(a+j)=temp;
      }
  else
     for(i=1,j=n+1;i<n;i+=2,j+=2)
     {
      temp=*(a+i);
      *(a+i)=*(a+j);
      *(a+j)=temp;
      }


  for(i=0;i<n*2;i++)
    printf(" %d",*(a+i));
  printf("\n");
  }

180 楼

9. 四人玩火柴棍游戏,每一次都是三个人赢,一个人输。输的人要按赢者手中的火柴
  数进行赔偿,即赢者手中有多少根火柴棍,输者就赔偿多少根。现知道玩过四次后, 每人恰好输过一次, 而且每人手中都正好有16根火柴。问此四人做游戏前手中各有 多少根火柴? 编程解决此问题

#include <stdio.h>
int main()
    {
       int arr[4]={16,16,16,16},i,j;
       for(j=3;j>=0;j--)
        for(i=0;i<=3;i++)
           if(i!=j){arr[i]/=2;arr[j]+=arr[i];}
       for(i=0;i<=3;i++)printf("%d ",arr[i]);
       getch();
       return 0;
       }

我来回复

您尚未登录,请登录后再回复。点此登录或注册