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

本文主要是介绍算法分析与设计——算法问题求解基础，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、实验目的

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）和递归部分。基础情况以直接形式明确列举新事物的若干简单对象，递归部分给出由简单（或较简单）对象定义新对象的条件和方法。

三、实验内容

1. 给定一个n个字符组成的串（称为文本），一个m（m<.n）个字符组成的串（称为模式），从文本中寻找匹配模式的子串。
   建模：给定两个字符串text和pattern，长度分别为n和m(n>m)，判断pattern是否在text中出现，如果出现则返回出现的位置，否则返回-1。

实验原理：
将模式对准文本的前m个字符从左往右进行比对，如果其中有一个字符不匹配，模式往右移动一位继续下一个m个字符的比对。最坏的情形是模式须移动n-m+1次，每次移动模式之前，做足m次比对才发现不匹配。因此，在最坏情况下，该算法属于Θ(nm)。
检查匹配串的第一个字符与文本串的第一个字符是否相匹配，我们通过比较文本串的和匹配串的第一个字符来开始，如果他们不匹配我们移向文本串的第二个字符。再比较匹配串的第一个字符和文本串第二个字符。如果他们不匹配我们继续向前移动,直到我们遇到一个相匹配的或直到我们到达文本串的最后。
实验代码：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int StringMatch(string T,string s)
{
	int n = T.size();       //文本长度
	int m = s.size();           //模式长度
	for (int i = 0; i < n - m; i++) //只需比较前n-m个字符
	{
		int j = 0;
		while (j < m&&s[j] == T[i + j])    //查找符合的
			j++;
		if (j == m)           //匹配成功返回模式在文本中的开始位置
			return i;
	}
	return -1;      //否则返回-1
}

int main()
{
	string T, P;
	cout << "请输入字符串文本：" <<endl;
	cin >> T;
	cout << "请输入待查字符串，寻找位置：" <<endl;
	cin >> P;   //输入一个标准文本和一个待查字符串
	cout << StringMatch(T, P) << endl;   //调用函数，输出查找结果
    return 0;
}

实验测试：
1.编译运行

2.数据测试：
①以hjdjgs54621ahgd545和1ah为测试，成功找到

②以hsgdh54和sdga为测试，返回-1，未找到

算法复杂度分析：
该方法又称暴力搜索，也是最容易想到的方法。预处理时间 O(0)，匹配时间复杂度O(N*M)。主要过程：从原字符串开始搜索，若出现不能匹配，则从原搜索位置+1继续。

2. 输入：一个升序数组A[0…n-1]和一个查找键K，用折半查找算法实现如下功能，输出：一个数组元素的下标，该元素等于K；如果没有这样一个元素，则返回-1。

实验原理：
比较x和a的中间元素a[mid]，若x=a[mid]，则x在L中的位置就是mid；如果x<a[mid]，则x在a[mid]的前面；如果x>a[mid]，则x在a[mid]的后面。无论在哪部分查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。

实验代码：

#include <iostream>
using namespace std;

int binary_search(int arr[], int length, int K);   //折半查找函数声明

int main()
{
    int i,k;
    int arr[10];  //定义待查找数组
    cout << "请输入长度为10的整型数组:" << endl;
    for(i=0;i<10;i++)
        cin >> arr[i];  //获取用户输入作为数组值
    cout << "请输入查找键K:" << endl;
    cin >> k;  //用户输入查找键K
    int id =  binary_search(arr, 10, k);  //调用折半查找函数

    cout << "id:" << id << endl;  //输出下标

    return 0;
}

int binary_search(int arr[], int length, int K)  //折半查找函数定义
{
    int n = length;
    int l = 0;
    int r = n - 1;  //获取数组长度n，以及首尾位置 l，r

    while(l <= r){
        int m = (int) (l+r) / 2;  //定义m为中间位置
        if(K == arr[m])return m;  //如果碰巧K等于中间值，直接返回
        else if(K < arr[m]) r = m-1;
        else l = m+1;  //否则继续比较前后位置
    }
    return -1;
}

实验测试：

1.编译运行

2.数据测试
①以2 4 8 12 46 48 78 79 81 83和81为测试，成功找到

②以2 4 8 12 46 48 78 79 81 83和56为测试，返回-1，未找到

算法复杂度分析：
输入规模：n
基本操作：三路数值比较
复杂度：

3. 我国古代数学家张丘建在《算经》一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

实验原理：
鸡翁一值钱五：公鸡五文一只;
鸡母一值钱三：母鸡三文一只；
鸡雏三值钱一：小鸡三只一文；
百钱买百鸡：100文钱买鸡。
设鸡翁x只，鸡母y只，鸡雏z只，所以5x+3y+1/3z = 100，x+y+z = 100
且x，y，z为整数， 0 <= x <= 100， 0 <= y <= 100， 0 <= z <= 100
如果用解方程的方式解这道题需要进行多次猜解，计算机的一个优势就是计算速度特别暴力并且无怨无悔，所以我们可以欺负她、蹂躏她！因此我们用穷举法的方式来解题，需要 1013 次猜解，但对于计算机来说，小 CASE！

分析：
这是一个很简单的for循环查找判断题。三种鸡均为整型，公鸡，母鸡不会出问题，但这鸡雏却会出现问题，在C中如果a 为int型，那么a/3等等仍然
为int型，假设a为2 则a/3输出的结果为0；a为4输出为1…所以要对鸡雏单独加一个判定条件(k % 3 == 0)。如果不想输出这么多次，可以把i，j，k拿到外边。如果想更进一步，及用宏定义来表示三种鸡型和它们的数量。先假设一只公鸡的数量最多是100/5=20，也就是公鸡最多的数量是20只，母鸡的数量最多为100/3=33（取整），小鸡的话因为最多只能有100只，所以小鸡最多的数量为100。

实验代码：

//暴力破解版
#include <stdio.h>

int main()
{
    int i, j, k;  //定义对三种鸡型的循环变量
    printf("穷举法的方式来解题,计算机计算结果：\n\n");
    for(i=0;i<=(100/5);i++ )   //鸡翁最多20只
        for(j=0;j<=(100/3);j++)  //鸡母最多33只
            for(k=0;k<=100;k++ )  //鸡雏最多100只
            {
                if(5*i+3*j+k/3==100&&k%3==0&&i+j+k==100)
                //如果数量满足百元买百鸡，则输出该配合
                {
                    printf("鸡翁%2d只,鸡母%2d只,鸡雏%2d只\n", i, j, k);
                }
            }
    return 0;
}

实验测试：

算法复杂度分析：
穷举法，使用三重循环，是最没有效率的算法。时间复杂度O(n ^ 3)，循环要执行1000000次，穷举法时间复杂度太高，可以进行适当的优化。如果小鸡的数量可以直接通过母鸡的数量和公鸡的数量算出来，算法简化成了二重循环，算法的时间复杂度为O(n ^ 2）。算法其实还可以继续优化成O(n),通过数学的方法，我们可以列出题目的方程组，设公鸡为x，母鸡为y,小鸡为z

换成参数方程：

根据题目定义域，列方程：

最后，算法被优化成了O(n),并且整个循环只要执行3次。
从一开始的穷举法需要执行1000000次，再到现在的只需要执行3次。

这篇关于算法分析与设计——算法问题求解基础的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！