算法分析与设计——算法问题求解基础

2021-09-01 07:15:31

一、实验目的

1.熟悉C/C++语言的集成开发环境;
2.掌握算法的概念；
3.了解问题的求解方法；
4.理解递归思想，学会编写递归。

二、实验原理

  • 算法（algorithm）
    一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有下列 5个特征: 输入（input）；输出（output）；确定性（definiteness）；能行性（effectiveness）；有穷性（finiteness）。
  • 问题求解过程
    理解问题（understand the problem）；
    设计方案（devise a plan）；
    实现方案（carry out theplan）；
    回顾复查（look back）。
  • 递归（recursive）
    递归定义是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况（base case）和递归部分。基础情况以直接形式明确列举新事物的若干简单对象，递归部分给出由简单（或较简单）对象定义新对象的条件和方法。

三、实验内容

假币问题

描述：

赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。

输入：

第一行有一个数字n，表示有n组测试用例。

对于每组测试用例：

输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用``up'', ``down'', 或 ``even''表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。

输出：

输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)。

样例输入：

1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even

样例输出：
K is the counterfeit coin and it is light.

解题思路 ：

  • 样例输入有3行数据，每行数据有三个字符串，每个字符串长度不超过6个（左右两边最多各放6个银币）。因此，首先设置三个数组来存放输入数据，分别是left[3][7]，right[3][7], result[3][7]。因此，
    left[0]=ABCD, right[0]=EFGH, result[0]= even
    left[1]= ABCI, right[1]= EFJK, result[1]= up
    left[2]= ABIJ, right[2]= EFGH, result[2]= even

  • 银币重量怎么表示？12个银币分别用ABCDEF….L来表示，A是第一个银币, B是第二个银币，… L是第12个银币，假设用数组status来存放银币重量：
    A ------> status[0]
    B ------> status[1]
    C ------> status[2]
    D ------> status[3]
    …
    L ------> status[12]

    先给12个银币的重量赋值

 for(i=0;i<12;i++)  status[i]=0

每个金币有两种情况，所以采用枚举法，变量分别是每个金币的编号x和轻重2种情况。在所有可能的24种猜测中，枚举每个金币及其轻重，当满足所有条件时为假设成立。
for(i=0;i<12;i++)
假设轻银币重量为-1 status[i]=-1;if (isBalance()) break;
假设重银币重量为1； status[i]=1; if (isBalance()) break;
假设正常银币重量为0 status[i]=0;

  • ABCD EFGH even：天平左边放ABCD四个银币，右边放EFGH四个银币，状态是even；即left=A银币的重量+ B银币的重量+ C银币的重量+ D银币的重量，right=E银币的重量+ F银币的重量+ G银币的重量+ H银币的重量。将银币重量带入，判断是否满足条件。如果满足输出true，否则输出false。
bool isBalance()
{
  for(i=0;i<3;i++)
   {
leftw=rightw=0;
     for(j=0;j<6 && left[i][j]！=0;j++)
     {
      leftw+=status[left[i][j]-‘A’];
rightw+=status[right[i][j]-‘A’];
 }
If (leftw== rightw && result[i][0]!=’e’)
     return false;
If (leftw> rightw && result[i][0]!=’u’)
     return false;
If (leftw< rightw && result[i][0]!=’d’)
     return false;
}
return true;
}

问题分析：
根据给定的条件，标记银币重量是否正确的做法是难以得到需要的答案的。
暴力法是必要的。12枚银币分别是A-L，那么A-L都有可能重了或轻了，共有24种情况，分别试一下就知道了。

代码：

#include <stdio.h>
#include <string.h>

#define N  3
#define M 8
char left2[N][M], right2[N][M], result[N][M];

int judge(char c, int heavy)
{
    int i;
    for(i = 0; i < N; i++) {
        if(result[i][0] == 'e') {
            if(strchr(left2[i], c) != NULL || strchr(right2[i], c) != NULL)
                return 0;
        } else if(result[i][0] == 'u') {
            if(heavy) {
                if(strchr(left2[i], c) == NULL)
                    return 0;
            } else {
                if(strchr(right2[i], c) == NULL)
                    return 0;
            }
        } else if(result[i][0] == 'd') {
            if(heavy) {
                if(strchr(right2[i], c) == NULL)
                    return 0;
            } else {
                if(strchr(left2[i], c) == NULL)
                    return 0;
            }
        }
    }
    return 1;
}

int main()
{
    int n,i;
    char c;
    scanf("%d", &n);
    while(n--) {
        for(i = 0; i < N; i++)
            scanf("%s%s%s", left2[i], right2[i], result[i]);

        for(c = 'A'; c <= 'L'; c++) {
            if(judge(c, 1)) {
                printf("%c is the counterfeit coin and it is heavy.\n", c);
                break;
            }
            if(judge(c, 0)) {
                printf("%c is the counterfeit coin and it is light.\n", c);
                break;
            }
        }
    }

    return 0;
}

编译执行：
算法分析与设计——算法问题求解基础
运行：
算法分析与设计——算法问题求解基础

4148:生理周期

描述：
人生来就有三个生理周期，分别为体力周期、感情周期和智力周期，它们的周期长度分别为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，在智力周期的高峰，人会思维敏捷，注意力容易高度集中。因为三个周期的长度不同，所以通常三个周期的高峰不会落在同一天。对于每个人，想知道何时三个高峰落在同一天。对于每个周期，会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。给定一个从当年第一天开始的天数，你的任务是输出从给定时间开始（不包括给定时间），下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同一天的时间是12，则输出2（注意这里不是3）。

输入：
输入包含多组数据，每一组数据由四个整数组成，数据以-1 -1 -1 -1 结束。对于四个整数p, e, i和d，p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d是给定的时间，可能小于p, e或i。所有给定时间是非负的并且小于或等于365，所求的时间小于或等于21252。

输出：
从给定时间起，下一次三个高峰同一天的时间（距离给定时间的天数）。

样例输入：
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
样例输出：
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.

解题思路：
这里可以这样理解，如果第n天满足条件，那么肯定三个周期经历了n1，n2,n3个轮回，加上初始化的天数，都等于n，也就是说，假设第1024天符合条件，那么对于例子中的第3行，必定有：1024=23n1+5，1024=28n2+20，1024=33*n3+34，所以，只要判断，这一天是不是符合条件：(d-5)%23 == 0 && (d-20)%28 == 0 && (d-34)%33 == 0，枚举即可。

代码：

#include <iostream>
#include <vector>
#include <cmath>
#include <stdio.h>
using namespace std;



int main() {

	int p, e, i;// 我身上搞三个指标p e i，每隔一段时间高峰一次，求哪一天三个指标都高峰了
	int d; //指定日期
	int cnt = 1;
	//23 28 33
	while (cin >> p >> e >> i >> d) {
		if (p == -1 && e == -1 && i == -1 && d == -1) {
			return 0;
		}

		/*
		假设日子是k(遍历k： d+1 ~ 21252)，三高峰出现的时机：
		(k - p) % 23 == 0  // 距离上一次高峰23天，所以今天k是p指标高峰
		(k - e) % 28 == 0 // 距离上一次高峰28天，所以今天k是e指标高峰
		(k - i) % 33 == 0 // 距离上一次高峰33天，所以今天k是i指标高峰
		*/

		int k;
		for (k = d + 1; (k - p) % 23 != 0; k ++); // 让k赋值了第一个p高峰
		for (; (k - e) % 28 != 0; k += 23); // 这时候k是双高峰
		for (; (k - i) % 33 != 0; k += 23 * 28); // 23 28的最小公倍数：23 * 28

		printf("Case %d: the next triple peak occurs in %d days.\n", cnt++, k - d);



	}

	return 0;
}

编译执行：
算法分析与设计——算法问题求解基础
运行：
算法分析与设计——算法问题求解基础

上一篇：RDS一键同步到新实例


下一篇：Java集合（8）--集合工具类Collections