算法练习（三）

川长思鸟来 2021-12-21 15:23 275阅读 0赞

# 一、侦察队问题 #

某侦察队接到一项紧急任务，要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人，但有以下限制条件：

1)A和B两人中至少去一人；

2)A和D不能一起去；

3)A、E和F三人中要派两人去；

4)B和C都去或都不去；

5)C和D两人中去一个；

6)若D不去，则E也不去。

试编写一个程序，输出问应当让哪几个人去？

## 代码 ##

#include<stdio.h>
    
    int main() {
        int a[6],b[6][6],i,sum=0,k=0; // a[0]~a[5]分别代表A~F。其值为0，代表不在队伍中；为1，代表在队伍中
        for (a[0] = 0; a[0] < 2; a[0]++) { // A
        for (a[1] = 0; a[1] < 2; a[1]++) { // B
        for (a[2] = 0; a[2] < 2; a[2]++) { // C
        for (a[3] = 0; a[3] < 2; a[3]++) { // D
        for (a[4] = 0; a[4] < 2; a[4]++) { // E
        for (a[5] = 0; a[5] < 2; a[5]++) { // F
            if ((a[0]||a[1]) && !(a[0]&&a[3]) && ((a[0]&&a[4]&&!a[5])||(a[0]&&!a[4]&&a[5])||(!a[0]&&a[4]&&a[5])) && ((a[1]&&a[2])||(!a[1]&&!a[2])) && ((a[2]&&!a[3])||(!a[2]&&a[3])) && (a[3]||!a[4])) {  // 进行逻辑判断，符合题目所给逻辑，则计算队伍人数并存储在二维数组中。
                for (i = 0; i < 6; i++) {
                    if (a[i] == 1) {
                        sum++;                  
                    }           
                }
                for (i = 0; i < 6; i++) {
                    b[sum][i] = a[i]; // 第一个下标为队伍总人数
                }
                if (sum > k) { // 刷新符合要求的最大人数
                    k = sum;
                }
            }
        }}}}}
        sum = 0;
        }
        // 从A~F依次表示其是否在队伍中
        for (i = 0; i < 6; i++) {
            printf("%d ",b[k][i]);
        }
        printf("\n");
        return 0;
    }

## 解题思路 ##

将六个人是否在队伍中的**状态**用**0（不在）**与**1（在）**来表示。暴力其所有可能的情况，判断每种情况是否满足条件，满足则统计其个数，并储存。最后输出人数最多组的安排情况。

### 要点 ###

表示此题6个逻辑要求是此题的要点。表示方法为：

1.  A和B两人中至少去一人 ——> a\[0\] || a\[1\]
2.  A和D不能一起去 ——> !(a\[0\]&&a\[3\])
3.  A、E和F三人中要派两人去 ——> (a\[0\]&&a\[4\]&&!a\[5\]) || (a\[0\]&&!a\[4\]&&a\[5\]) || (!a\[0\]&&a\[4\]&&a\[5\])
4.  B和C都去或都不去 ——> (a\[1\]&&a\[2\]) || (!a\[1\]&&!a\[2\])
5.  C和D两人中去一个 ——> (a\[2\]&&!a\[3\]) || (!a\[2\]&&a\[3\])
6.  若D不去，则E也不去 ——> a\[3\] || !a\[4\]

### 有个更好的方式表示该题逻辑 ###

if(a+b>=1&&a+d!=2&&a+e+f==2&&b==c&&c+d==1&&(d+e==0||d==1))

这样更简单。但是我没想到。。。

# 二、奇怪的分式 #

上小学的时候，小明经常自己发明新算法。一次，老师出的题目是：1/4 乘以 8/5

小明居然把分子拼接在一起，分母拼接在一起，答案是：18/45

老师刚想批评他，转念一想，这个答案凑巧也对啊，真是见鬼！

对于分子、分母都是1~9中的一位数的情况，还有哪些算式可以这样计算呢？  
请写出所有不同算式的个数（包括题中举例的）。  
显然，交换分子分母后，例如：4/1 乘以 5/8 是满足要求的，这算做不同的算式。

但对于分子分母相同的情况，2/2 乘以 3/3 这样的类型太多了，不在计数之列!

### 注意：答案是个整数（考虑对称性，肯定是偶数）。 ###

## 代码 ##

#include<stdio.h>
    
    int main() {
        int a,b,c,d,sum = 0;
        for (a = 1; a < 10; a++) {
        for (b = 1; b < 10; b++) {
        for (c = 1; c < 10; c++) {
        for (d = 1; d < 10; d++) {
            if (a != b && c != d) {  // 确保两个分式的分子与分母都不相同 
                if ((a*c)*(b*10 + d) == (b*d)*(a*10 + c)) {
                    sum++;
                }
            }
        }}}}
        printf("%d",sum);
        return 0;
    }

## 解题思路 ##

题目的思路简单，遍历所有情况，满足条件则进行计数。  
题目的要点在于变化方程形式，将除法的比较转变为乘法的比较。这样可以避免整型相除的误差。

### 附：python代码： ###

sum = 0
    for a in range(1,10):
        for b in range(1,10):
            for c in range(1,10):
                for d in range(1,10):
                    if a != b and c != d:    #确保两个分式的分子与分母都不相同 
                        if (a*c)*(b*10 + d) == (b*d)*(a*10 + c):
                            sum+=1
    print(sum)

# 附：[Shape Of My Heart][] #

![1084569-20170709181641822-842628563.jpg][]

以上

转载于:https://www.cnblogs.com/mxwbq/p/7142363.html

[Shape Of My Heart]: http://music.163.com/m/song?id=1934649&userid=319856411
[1084569-20170709181641822-842628563.jpg]: /images/20211220/24a47aaafb804ee49e1d89171802d123.png