精华内容
下载资源
问答
  • React Fiber是React核心算法的不断重新实现。 这是React团队经过两年多研究的结晶。 React Fiber的目标是提高其动画,布局和手势等区域的适用性。 它的标题功能是增量渲染:将渲染工作分成多个块并将其分布到多...
  • 多元统计分析课程设计 R Apriori 设计题目基于 语言 算法在挖掘商品交易数据中应用 摘 要 Apriori 算法是一种挖掘关联规则频繁项集算法广泛应用于商业领域与 R arules Apriori 网络安全领域描述了使用 ...
  • 算法设计另一有效算法为分治算法,分治算法包括两步: 1)分(divide):递归解决较小问题(当然基本情况除外); 2)治(conquer):从子问题中构建原问题解; 可以看到,在之前归并排序、快速排序...

    算法设计技巧二:分治算法(divide and conquer)

           算法设计的另一有效算法为分治算法,分治算法包括两步:

                    1)分(divide):递归解决较小的问题(当然基本情况除外);

                    2)治(conquer):从子问题中构建原问题的解;

            可以看到,在之前的归并排序快速排序、以及无向图深度优先搜索有向图深度优先搜索等方法中,有效的应用的分的思想,但并未实现治的部分,因此,不能算作分治算法。即正文中至少含有两个递归调用的例程才能成为分治算法。

            分治算法的典型实例为最大子序列求和问题实现O(N\log N)解。实现斐波拉契数列时使用递归可以看做是分治算法的一个糟糕的实例(通过非递归调用将更有效)。但这并不意味着分治算法总是很糟糕。在本篇将通过使用一般方法和分治算法求解最近点对问题,通过对比,证明分治算法的有效时间界。

    分治算法的运行时间:

            分治算法存在从N-1步到第N步的递推表示:f(N) = f(N-1)。举例常见的两种形式及其对应的解【证明略】。

     最近点对问题:

            给定平面上的一系列点,求解最近两点的距离及坐标。若点的数量为N,则存在N(N-1)/2个点对,使用一般方式,逐步比较最近点距离将花费O(N^2)时间,通过分治算法有望实现O(N\log N)时间。

           分支算法实现步骤:

                  1)点数小于等于3直接使用一般方法求解,点数大于3时将平面按x轴排序,取排序中点为分割线,将平面分割成YL和              YR两部分,递归求解YL和YR平面的最小距离left和right;d = min(left, right),如果存在最近点对(P1,P2)(P_1,P_2)位于分割线内距离小于d,则对带状区域内的每一个点检测y_i\pm d内的7个点,求解距离d',则minDis = min(d,d')。图示如下:

    最近点问题编程实现:

    //main.cpp
    #include<iostream>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<ctime>
    
    using namespace std;
    const int REPEAT = 100; //repeat REPEAT time to calcuate the time
    
    class myPoint {
    public:
        float x;
        float y;
    };
    
    //compare point a and b controlled by type
    bool compare(myPoint a, myPoint b, int type) {
        if (type == 1) {
            return a.x > b.x;
        }
        else {
            return a.y > b.y;
        }
    }
    void Initial(int N, myPoint* X, myPoint* Y) {
        srand(time(0));  //get the system clock 
        int i;
        for (i = 0; i < N; i++) {  //generate the random value [-10, 10]
            X[i].x = rand() / double(RAND_MAX)*20 - 10;
            X[i].y = rand() / double(RAND_MAX)*20 - 10;
            Y[i].x = X[i].x;
            Y[i].y = X[i].y;
            cout << "The rand pair is : (" << X[i].x << ", " << X[i].y << " ) " << endl;
        }
    }
    double Distance(myPoint p1, myPoint p2) {  //calcuate the distance
        return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
    }
    
    //quickSort the axis value controlled by type
    void quickSort(myPoint* P, int start, int end, int type) {
        if (start == end)	//only one point
            return;
        int primary_start = start; 		//save the original start
        int primart_end = end;			//save the original end
        myPoint pivotKey = P[start]; 	//set pivotKey
    
        while (start < end)		//quickSort algrithm
        {	//find the right border
            while (start < end && compare(P[end], pivotKey, type))
            {
                end--;
            }
            //update the start
            if (start < end) {
                P[start++] = P[end];
            }
            //find the left border
            while (start < end &&  compare(pivotKey, P[start], type))
            {
                start++;
            }
            //update the end
            if (start < end) {
                P[end--] = P[start];
            }
        }
        //update pivotKey when start = end
        P[start] = pivotKey;
    	
    	//quickSort the left part
        if (start - 1>primary_start){
        	quickSort(P, primary_start, start - 1, type);
        }
    	//quickSort the right part
        if (start + 1<primart_end){
        	quickSort(P, start + 1, primart_end, type);
        }
    }
    
    //direct solve the nearest points
    double force(int start, int end, myPoint* P, myPoint& P1, myPoint& P2) {
        int i, j;
        if (end - start<1) {	//only one point
            return 0.0;
        }
        double minDis = Distance(P[start], P[start + 1]);  //init the minDis
        P1 = P[start];		//init P1
        P2 = P[start+1];	//init P2
        for (i = start; i <= end; i++) {
            for (j = start; j <= end; j++) {
                if (i != j && Distance(P[i], P[j])<minDis) {
                    minDis = Distance(P[i], P[j]);
                    P1 = P[i];
                    P2 = P[j];
                }
            }
        }
        return minDis;
    }
    
    //divide_conquer algrithm for nearest points
    double divide_conquer(int start, int end, myPoint* X, myPoint* Y, myPoint& P1, myPoint& P2) {
    
        if (end - start < 3){
            return force(start, end, X,P1,P2);
       }
       //divide
        int mid = (start + end) / 2; 
        int leftLen = 0, rightLen = 0, i, j; 
        myPoint* YL = new myPoint[(end - start + 1) ];//y left part
        myPoint* YR = new myPoint[(end - start + 1) ];//y right part
    	//conquer
        for (i = 0; i <= end - start; i++){
            if (Y[i].x <= X[mid].x) {
                YL[leftLen++] = Y[i];
            }
            else {
                YR[rightLen++] = Y[i];
            }
        }
        double left = divide_conquer(start, mid, X, YL,P1,P2);	//find the left minDis
        myPoint leftP1 = P1;			//save P1
        myPoint leftP2 = P2;			//save P2
        double right = divide_conquer(mid + 1, end, X, YR,P1,P2);  //find the right minDis
        double minDis;
        //take the minDis from left and right, refill P1 and P2
        if (left < right) {
            minDis = left;
            P1 = leftP1;
            P2 = leftP2;
        }
        else {
            minDis = right;
        }
        //setup the danding region
        myPoint* newY = new myPoint[(end - start + 1)];
        int newYLen = 0;
        double leftBorder = X[mid].x - minDis;
        double rightBorder = X[mid].x + minDis;
        //find the points in region
        for (i = 0; i <= end - start; i++) {
            if (Y[i].x >= leftBorder && Y[i].x <= rightBorder){
            	newY[newYLen++] = Y[i];
            }
        }
        //find the nearest 7 distance
        for (i = 0; i<newYLen; i++) {
            for (j = 1; j <= 7; j++) {
            	//keep the newY in region
                if ((i + j)<newYLen) {
                    double dis = Distance(newY[i], newY[i + j]);
                    if (dis < minDis) {
                        minDis = dis;
                        P1 = newY[i];
                        P2 = newY[i + j];
                    }
                }
            }
        }
        delete YL;
        delete YR;
        delete newY;
        return minDis;
    }
    int main(){
        int N;
        cout << "Enter the total number of points :";
        cin >> N;
        //create X and Y(same as X) points set
        myPoint* X = new myPoint[N];
        myPoint* Y = new myPoint[N];
        int i;
        clock_t start, end;
        double ave = 0.0;
        double minDis = 0.0;
        myPoint P1, P2; //init the nearest points result
        Initial(N, X, Y);	//instantiation the X and Y
        for (i = 0; i < REPEAT; i++) {	//repeat REPEAT times
            start = clock();
            minDis += force(0, N - 1, X,P1,P2);
            end = clock();
            ave += (double)(end - start);
        }
        ave /= REPEAT;
        minDis /= REPEAT;
        cout << "force: minDis : " << minDis << " time loss : " <<ave<<" ms" << setw(4);
        cout << " Position:(" << P1.x << "," << P1.y << "),(" << P2.x << "," << P2.y << ")"<<endl;
    
        ave = 0.0;
        minDis = 0.0;
        for (i = 0; i < REPEAT; i++) {  
            start = clock();
            quickSort(X, 0, N - 1, 1);	//sort X axis
            quickSort(Y, 0, N - 1, 2);	//sort Y axis
            minDis+= divide_conquer(0, N - 1, X, Y,P1, P2);
            end = clock();
            ave += (double)(end - start);
        }
        ave /= REPEAT;
        minDis /= REPEAT;
        cout << "divide_conquer: minDis : " <<minDis<< " time loss : " << ave << " ms" << setw(4);
        cout << " Position:(" << P1.x << "," << P1.y << "),(" << P2.x << "," << P2.y << ")" << endl;
        delete[]X;
        delete[]Y;
        return 0;
    }

    实验结果:

    N = 10时,直接求解稍快;

    N= 50时, 分治算法稍快;

    N=100时,分治算法明显更快;

           实验表明,在求解最近点对问题上,当点对数量较大时,分治算法具有更短的运行时间。在很大一类问题上,通过分支算法可以实现高效解法,如矩阵分块、多项式乘法等。

    practice makes perfect ! 

    展开全文
  • 内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。《数据结构与算法分析:C++描述(第3版)》适合作为计算机相关专业本科...
  • 程序流程的描述称为算法(algorithm) 在程序中,程序的流程控制语句是用语句(statement)来实现的,它指定了表达式的计算次序。 程序流程控制包括:选择和循环 选择执行是指根据某个条件满足与否来决定是否...

    3.1 概述

    • 程序流程的描述称为算法(algorithm)
    • 在程序中,程序的流程控制语句是用语句(statement)来实现的,它指定了表达式的计算次序。
    • 程序流程控制包括:选择和循环
      • 选择执行是指根据某个条件满足与否来决定是否执行某个语句
      • 循环执行是指根据某个条件是否满足来决定是否重复执行某个语句

     

    • 设计流程控制时,可先用程序流程图(flowchat)来对程序流程进行描述,然后用编程语言写出程序。

     

    • 从语句的语法构成上,可分为简单语句与结构语句
      • 简单语句:不包含其他语句的语句
        • 表达式语句
        • 无条件转移语句
        • 空语句
      • 结构语句:简单语句和结构语句按一定规则构造出来的语句
        • 复合语句
        • 选择语句
        • 循环语句

     

    • C++中的语句
      • 顺序执行语句
        • 表达式语句、复合语句、空语句
      • 选择执行语句
        • if语句、switch语句
      • 循环执行语句
        • while语句、while-do语句、for语句
      • 无条件转移语句
        • goto语句、break语句、contiune语句、return语句
      • 数据定义语句(C++可以在数据定义时对其初始化,使得数据定义也包含操作

    3.2 顺序执行

    C++支持顺序执行的语句有:表达式语句、复合语句、空语句

     

    3.2.1 表达式语句

    在C++表达式的后面加上一个分号“;”就可以构成表达式语句(expression statement,常用语句包括:赋值、自增/自减输入/输出、无返回值的函数调用

     

    1、从键盘输入一个数,然后输出该数的平方、立方以及平方根

    void Expression::test1(){

    double x;

    cout<<"请输入一个数:"<<endl;

    cin>>x;

    cout<<x<<"的平方是:"<<x*x<<endl;

    cout<<x<<"的立方是:"<<x*x*x<<endl;

    cout<<x<<"的平方根是:"<<sqrt(x)<<endl;

    }

     

    2、计算a+2a+3a+...的前n项的和

    void Expression::test2(){

     

    int n;

    double a;

    cout<<"请输入首项:"<<endl;

    cin>>a;

    cout<<"请输入项数:"<<endl;

    cin>>n;

    cout<<"前n项的和为:"<<(a+a*n)*n/2<<endl;

     

    }

     

    3.2.2 复合语句

    复合语句(compound statement是由一对花括号({ })括起来的一个或多个语句构成,又称为块(block)。复合语句的格式为:

    { <语句序列> }

    复合语句主要用作结构语句的成分语句函数体,注意花括号的配对问题

     

    3.2.3 空语句

    空操作在C++中用空语句实现,空语句的格式为:

    空语句的作用是用于语法上需要一条语句的地方,而该地方又不需要做任何事

    {

    ...

    ... goto end;

    ... ...

    end: ; //空语句

    }

     

    注意:

    在分号(;)的使用上,一些语言是作为语句之间的分隔符,语句本身不包含分号;C++中,分号作为语句的结束符,是语句的一部分


    3.3 选择执行

    选择控制(selection control)又叫分支(branching)控制,是通过if语句和switch语句实现的

     

    3.3.1 if语句

     

    1、从键盘中输入三个整数,输出最大数

    #include<iostream>
    
    using namespace std;
    
     
    
    //从键盘中输入三个整数,输出最大数
    
    void Selection::test1(){
    
     
    
    inta,b,c;
    
    cout<<"请输入三个整数,用\"空格或回车\"隔开:"<<endl;
    
    cin>>a>>b>>c;
    
     
    
    //cout<<"请输入第1个数:"<<endl;
    
    //cin>>a;
    
    //cout<<"请输入第2个数:"<<endl;
    
    //cin>>b;
    
    //cout<<"请输入第3个数:"<<endl;
    
    //cin>>c;
    
     
    
    if(a>=b){
    
    if(a>c){
    
    cout<<"最大数为"<<a<<endl;
    
    }else{
    
    cout<<"最大数为"<<c<<endl;
    
    }
    
    }else{
    
    if(b>c){
    
    cout<<"最大数为"<<b<<endl;
    
    }else{
    
    cout<<"最大数为"<<c<<endl;
    
    }
    
    }
    
     
    
    }
    
    

     

    2、输入a、b、c,求一元二次方程ax^2+bx+c=0的实根

     

    void Selection::test2(){
    
    //输入a、b、c,求一元二次方程ax2+bx+c=0的实根
    
    double a,b,c;
    
    cout<<"请输入a、b、c的值,用\"空格或回车\"隔开:"<<endl;
    
    cin>>a>>b>>c;
    
    if((b*b-4*a*c)<0){
    
    cout<<"该方程没有实数根"<<endl;
    
    }elseif((b*b-4*a*c)==0){
    
    cout<<"该方程有两个相等的实数根,x1=x2="<<-b/(2*a)<<endl;
    
    }else{
    
    cout<<"该方程有两个不相等的实数根,x1="<<(-b+sqrt(b*b-4*a*c))/(2*a)<<",x2="<<(-b-sqrt(b*b-4*a*c))/(2*a)<<endl;
    
    }
    
     
    
    }

     

     

    3、输入三角形的三边长,判断其为何种三角形

     

    void Selection::test3(){
    
    double a,b,c;
    
    cout<<"请输入a、b、c的值,用\"空格或回车\"隔开:"<<endl;
    
    cin>>a>>b>>c;
    
    boolab=Selection::cmpFloat(a,b);
    
    boolbc=Selection::cmpFloat(b,c);
    
    boolrt=((a*a+b*b==c*c)||(a*a==b*b+c*c)||(b*b==a*a+c*c));
    
    if((a+b)>c&&(a+c)>b&&(b+c)>=a){
    
    if((ab|bc)&&(ab&bc)==0){
    
    cout<<"等腰三角形"<<endl;
    
    }elseif(ab&bc){
    
    cout<<"等边三角形"<<endl;
    
    }elseif((bool)(ab|bc)&rt){
    
    cout<<"等腰直角三角形"<<endl;
    
    }elseif(rt){
    
    cout<<"直角三角形"<<endl;
    
    }else{
    
    cout<<"三角形"<<endl;
    
    }
    
    }else{
    
    cout<<"不是三角形"<<endl;
    
    }
    
    }

     

     

    4、从键盘输入两个表示时刻的时间数据(时、分、秒),比较两个时刻的先后次序

     

    void Selection::test4(){
    
    int h1,h2,m1,m2,s1,s2;
    
    cout<<"输入第一个时刻(时分秒)"<<endl;
    
    cin>>h1>>m1>>s1;
    
    cout<<"输入第二个时刻(时分秒)"<<endl;
    
    cin>>h2>>m2>>s2;
    
    if(0<=h1&&h1<=24&&0<=m1&&m1<=60&&s1>=0&&s1<=60&&0<=h2&&h2<=24&&0<=m2&&m2<=60&&s2>=0&&s2<=60){
    
    if(h1>h2){
    
    cout<<"第二个时刻在前"<<endl;
    
    }elseif(h1<h2){
    
    cout<<"第一个时刻在前"<<endl;
    
    }elseif(m1>m2){
    
    cout<<"第二个时刻在前"<<endl;
    
    }elseif(m1<m2){
    
    cout<<"第一个时刻在前"<<endl;
    
    }elseif(s1>s2){
    
    cout<<"第二个时刻在前"<<endl;
    
    }elseif(s1<s2){
    
    cout<<"第一个时刻在前"<<endl;
    
    }
    
    }else{
    
    cout<<"输入时刻不正确"<<endl;
    
    }
    
     
    
    }

     

    if-else配对规则:“else子句与前面最近的,没有else子句的if配对”

     

     

    3.3.2 switch语句

    switch语句又称(开关语句),格式如下:

     

    switch (<整型表达式>){

    case <整型常量表达式1>:<语句序列1>

    case <整型常量表达式2>:<语句序列2>

    ... ...

    case <整型常量表达式n>:<语句序列n>

    [default:<语句序列n+1>]

     

    }

     

    1、从键盘输入一个星期的一天(0:星期天,1:星期一,···),然后输出对应的英文

    void Selection::test5(){
    
    int a;
    
    cout<<"输出数字(0~6):"<<endl;
    
    cin>>a;
    
    cout<<"a="<<a<<endl;
    
    switch(a){
    
    case 0:cout<<"Sunday"<<endl;
    
    break;
    
    case 1:cout<<"Monday"<<endl;
    
    break;
    
    case 2:cout<<"Tuesday"<<endl;
    
    break;
    
    case 3:cout<<"Wednesday"<<endl;
    
    break;
    
    case 4:cout<<"Thursday"<<endl;
    
    break;
    
    case 5:cout<<"Friday"<<endl;
    
    break;
    
    case 6:cout<<"Saturday"<<endl;
    
    break;
    
    default:cout<<"inputerror"<<endl;
    
    break;
    
    }
    
    }

     

    注意:1、当输入为首字符不为数字的字符串时,C++默认转为int值为0。如:df、er32等

       2、当输入首字符为数字的字符串时,C++将其转为int时,保留首字符数字。如2er转为2、43rf3转为43等

     

    2、计算某年某月的天数

    void Selection::test6(){
    
     
    
    //计算某年某月的天数
    
    intyear,month;
    
    cout<<"输入年份月数"<<endl;
    
    cin>>year>>month;
    
    switch(month){
    
    case 2:
    
    if((year%4==0||year%400==0)&&year%100!=0){
    
    cout<<year<<"年"<<month<<"月共29天"<<endl;
    
    }else{
    
    cout<<year<<"年"<<month<<"月共28天"<<endl;
    
    }
    
    break;
    
    case 1:case 3:case 5:case 7:case 8:case 10:case 12:
    
    cout<<year<<"年"<<month<<"月共31天"<<endl;
    
    break;
    
    case 4:case 6:case 9:case 11:
    
    cout<<year<<"年"<<month<<"月共30天"<<endl;
    
    break;
    
    }
    
     
    
    }
    
    

    3.4 循环(重复)执行

    3.4.1 迭代与穷举

    代码的重复执行机制一般有两种:循环和递归

    循环(loop)是指重复执行一组语句知道某个条件满足(或不满足)为止。由四部分组成:

    • 循环初始化——用于为重复执行的语句提供初始数据
    • 循环条件——描述了重复操作需要满足的条件
    • 循环体——要重复执行的语句
    • 下一次循环准备——为下一次循环更新数据

     

    循环控制可实现问题求解的迭代法和穷举法

    • 迭代法:对待问题先指定一个近似的初始解,然后按照某种规则基于这个初始解计算出下一个近似解,知道某个条件满足后得到最终解。如求n!
    • 穷举法:对所有“可能”的解逐一去验证它是否满足条件,满足条件则它是一个解,否则它不是解。

     

    C++提供三种循环语句:while、do-while、for语句。三种循环语句是等价的,用一种循环语句表示的操作一定能用其他两种循环语句表示出来。

     

    循环分为两大类:计数控制的循环(counter-controller loop事件控制的循环(evnet-controller loop

    • 计数控制的循环:对循环次数进行计数,重复执行循环体直到指定的次数,用for语句表达
    • 事件控制的循环:循环前不知道循环次数,循环的终止是由循环体满足结束条件引起的,又称条件控制循环(conditional loop),用while或do-while语句实现

    如果循环体至少执行一次,用do-while实现。

    有时

     

    3.4.2 while语句

    while(<表达式>) <语句>

    3.4.3 do-while语句

    do<语句>while(<表达式>)

    3.4.4 for语句

    for(<表达式1>;<表达式2>;<表达式3>)<语句>

     

    1、求n!

    void Loop::test1(){
    
    //求n!
    
    int n,m,sum;
    
    cout<<"输入n的值:"<<endl;
    
    cin>>n;
    
    //保存输入的值
    
    m=n;
    
    //保存结果
    
    sum=1;
    
     
    
    //使用while实现
    
    while(n>0){
    
    sum=n*sum;
    
    n--;
    
    }
    
     
    
    //使用for实现
    
    for(inti=1;i<=n;i++){
    
    sum=sum*i;
    
    }
    
     
    
    //使用do-while实现
    
    do{
    
    sum=n*sum;
    
    n--;
    
    }while(n>0);
    
     
    
    cout<<m<<"!="<<sum<<endl;
    
    }
    
    

    2、计算从键盘输入的一系列整数的和,要求首先输入整数的个数

    void Loop::test2(){
    
    int n,num,sum=0;
    
    cout<<"输入整数的个数:"<<endl;
    
    cin>>n;
    
    for(int i=0;i<n;i++){
    
    cout<<"请输入第"<<i+1<<"个数:"<<endl;
    
    cin>>num;
    
    sum=sum+num;
    
    }
    
    cout<<"这"<<n<<"个数的和为:"<<sum<<endl;
    
     
    
    }

     

    3、计算从键盘输入的一系列整数的和,要求输入以0结束

    void Loop::test5(){
    
     
    
    //计算从键盘输入的一系列整数的和,要求输入以0结束
    
    ints um=0,n;
    
    cout<<"请输入若干整数(以0结束):"<<endl;
    
    do{
    
    cin>>n;
    
    //cout<<"n为:"<<n<<endl;
    
    sum=sum+n;
    
    }while(n!=0);
    
    cout<<"和为:"<<sum<<endl;
    
     
    
    }

     

     

     

    4、从键盘接受字符,一直到输入字符y(Y)或n(N)为止

     

    void Loop::test6(){
    
     
    
    //从键盘接受字符,一直到输入字符y(Y)或n(N)为止
    
    //charn[]={};
    
    charc;
    
    //strings="";
    
    cout<<"请输入若干字符:"<<endl;
    
    do{
    
    cin>>c;
    
    cout<<"c为:"<<c<<endl;
    
    //s=s.append(to_string(n));
    
    }while(c!='y'&&c!='Y'&&c!='n'&&c!='N');
    
    //cout<<s<<endl;
    
    }
    
    

     

    5、判断键盘输入的一个整数是否为素数

     

    void Loop::test7(){
    
     
    
    //判断键盘输入的一个整数是否为素数
    
    intn;
    
    boolisPrime=true;
    
    cout<<"输入一个整数:"<<endl;
    
    cin>>n;
    
    if(n==0||n==1){
    
    isPrime=false;
    
    }else{
    
    for(inti=2;i<n;i++){
    
    if((n%i)==0){
    
    isPrime=false;
    
    break;
    
    }
    
    }
    
    }
    
    if(isPrime){
    
    cout<<n<<"为素数"<<endl;
    
    }else{
    
    cout<<n<<"不为素数"<<endl;
    
    }
    
     
    
     
    
    }

     

     

    6、求第n个斐波那契(Fibonacci)数

    Fibonacci数定义如下:

    𝑓𝑖𝑏(𝑛)1(𝑛=1)1(𝑛=2)𝑓𝑖𝑏𝑛−2+𝑓𝑖𝑏(𝑛−1)(𝑛≥3)

     

    void Loop::test8(){
    
    intn,f1=1,f2=1;
    
    cin>>n;
    
    if(n==1||n==2){
    
    cout<<"第"<<n<<"个斐波那契数为1"<<endl;
    
    }else{
    
    for(inti=3;i<=n;i++){
    
    inttmp=f1+f2;//计算新的斐波那契数
    
    f1=f2;//记住前一个斐波那契数
    
    f2=tmp;//记住新的斐波那契数
    
    }
    
    cout<<"第"<<n<<"个斐波那契数为"<<f2<<endl;
    
    }
    
    }
    
    
    	//递归
    int Function::fib(int n){
    if(n==1||n==2){
    	return 1;
    }else{
    	return fib(n-2)+fib(n-1);
    	}
    }
    

     

    7、用牛顿迭代法求3a

    𝑥𝑛+1=13(2𝑥𝑛+𝑎𝑥𝑛2),当|xn+1-xn|<ℇ(10-6)时,xn+1即为3a的值

     

     

    void Loop::test9(){
    
     
    
    const double EPS=1e-9;
    
    double a,x1,x2;
    
    cout<<"请输入一个数:"<<endl;
    
    cin>>a;
    
    x2=a;
    
    do{
    
    x1=x2;
    
    x2=(2*x1+a/(x1*x1))/3;
    
    }while(fabs(x2-x1)>=EPS);
    
    cout<<a<<"的立方根是"<<x2<<endl;
    
     
    
    }
    
    

     

     

     

    8、输出小于n的所有素数

     

    void Loop::test10(){
    
     
    
    //输出小于n的所有素数
    
    int n,count=1;
    
    cout<<"请输入一个数:"<<endl;
    
    cin>>n;
    
    if(n<=2){
    
    cout<<"输入错误。"<<endl;
    
    }
    
    cout<<2<<",";//输出第一个素数
    
    for(int i=3;i<n;i+=2){//循环,分别判断3、5、7、是否为素数
    
    int j=2,k=sqrt((double)i);//取i的平方根
    
    while((j<=k) && i%j!=0){
    
    j++;
    
    }
    
    if(j>k){
    
    cout<<i<<",";
    
    count++;
    
    if(count%6==0){
    
    cout<<endl;
    
    }
    
    }
    
    }
    
     
    
    }

     

     

    9、求级数1+x+x2/2!+...+xi/i!···前n项之和

     

    void Loop::test11(){
    
     
    
    double x;
    
    int n;
    
    cin>>x>>n;
    
    double item=x,sum=1+x;
    
    for(inti=2;i<n;++i){
    
    item *= x/i;
    
    sum += item;
    
    }
    
    cout<<"x="<<x<<",n="<<n<<",sum="<<sum<<endl;
    
     
    
    }

    3.5 无条件转移

    3.5.1 goto语句

    goto <语句标号>;

    • 含义:转向带有相应<语句标号>的语句
    • goto语句的使用可分为两类:向前的转移(forward)往回的转移(backward)
      • 向前的转移隐含的是分支结构,可用if语句实现
      • 往回的转移隐含着循环,可用循环语句实现
    • 理论上,所有程序都可以不用goto语句实现,保留goto的原因:
      1. 早期的程序流程控制大多采用goto和if语句来实现
      2. 某些情况下使用goto语句会带来便利(从多层内层循环跳到外层循环等)

     

    1、用goto语句求n!

    void Loop::test3(){
    
    int n;
    
    cin>>n;
    
    int i=1,f=1;
    
    loop:
    
    f*=i;
    
    i++;
    
    if(i<=n){
    
    goto loop;
    
    }
    
    cout<<"factorialof"<<n<<"="<<f<<endl;
    
    }
    
    

     

    注意:

    • 不能用goto语句从一个函数外部转入该函数的内部(函数体),也不能用goto语句从一个函数的内部转入该函数的外部。
    • goto语句不能掠过带有初始化的变量定义。
    • 慎重使用goto语句,它会破坏程序的一些良好的性质

     

    3.5.2 break语句

    break;

    • 含义
      1. 结束switch语句的某个分支的执行;
      2. 退出包含它的循环语句
        1. 在循环体中使用break语句,立即跳出循环,break后面的语句也不再执行
        2. 对于多重循环,内层循环语句循环体中的break语句只能用于结束内层循环语句的执行;要结束外层循环,则可以用goto语句

     

    3.5.3 contiune语句

    continue;

    • 只能在循环体中使用
    • 含义:立即结束当前循环,准备进入下一次循环
    • continue语句的功能可以用goto语句和带标号的空语句来实现

     

    2、从键盘输入一些非零整数,然后输出其中所有正数的平方根

     

    void Loop::test4(){
    
    int n;
    
    double square_root;
    
    cout<<"请输入若干整数(以0结束)"<<endl;
    
    for(cin>>n;n!=0;cin>>n){
    
    if(n<0)continue;
    
    square_root=sqrt((double)n);
    
    cout<<n<<"的平方根是"<<square_root<<endl;
    
    }
    
    }

     

     

    注意

    • continue与break的不同:continue只结束本次循环,break结束整个循环
    • continue与break的相同:循环体中continue后面的语句也将不再执行,并且continue语句一般也作为循环体中某个if语句的字句来使用
    • continue语句不是必须的,可以用循环语句实现;但有时会给循环体中的一些条件性动作带来便利

     


    3.6 小结

    •    语句用于实现对程序执行流程的控制,一系列语句构成了程序的算法描述

     

    • C++语句分为:简单语句结构语句
      • 简单语句包括表达式语句、转移语句和空语句;
        • 表达式语句由表达式加上一个分号“;”构成。常用的表达式语句是含有赋值、自增/自减、输入/输出以及函数调用等操作的表达式语句
        • 转移语句包括break、continue和goto
          • break语句用于终止switch语句的一个分支或循环语句的循环操作
          • continue语句用于结束当前循环的执行,准备进入下一次循环
          • goto语句用于转向带标号的语句执行
        • 空语句不做任何事情,其作用是用于语法上需要一条语句的地方,而该地方又不需做任何事情
      • 结构语句包括复合语句、选择语句和循环语句
        • 复合语句是由一对花括号“{}”括起来的一条或多条语句构成,又称为块(block)。在复合语句中,除了普通语句外,还可以包含局部数据的定义。
        • 选择语句包括:if语句和switch语句
          • if语句(又称条件语句)是根据一个条件满足与否来决定是否执行某个语句或从两个语句中选择一个语句执行
          • switch语句(又称开关语句)是根据某个表达式的值在多组语句中选择一组语句来执行
        • 循环(重复)语句是根据某个条件的满足与否来决定是否重复执行一组语句。
          • 循环一般有四个部分组成:循环初始化、循环条件、循环体和下一次循环准备
          • 循环可以分为两大类:计数控制的循环(一般用for语句实现)和事件控制的循环(用while或do-while实现)

     

    • 程序设计风格通常是指对程序进行静态分析所能确认的程序特性,它涉及程序的易读性

     

    • 结构化程序设计是指“按照一组能够提高程序易读性与易维护性的规则进行程序设计的方法”。一个结构化程序通常由三种语句构成:顺序、分支和循环,按结构化程序设计方法设计的程序具有良好的风格

    3.4.2 递归

    • 一个函数在其函数体中直接或间接调用了自己,该函数为递归函数(recursive function
      • 递归函数分为直接递归间接递归
      • 对递归函数的每一次调用都将产生一组局部变量,虽然它们名称相同,但它们是不同的变量,拥有不同的内存空间。递归调用可理解为函数的嵌套调用
    • “分而治之”的程序设计
      • 定义递归函数时,要对两种情况进行描述:
        1. 一般情况(general case:描述了问题的分解和综合过程,其中包含递归调用。
        2. 特殊情况(又称基础情况,base case:指出问题求解的特例,在该情况下不需递归就能得到结果。
    • 循环与递归的选择
      • 循环与递归的异同
        • 同:都可以实现重复操作
          • 循环是在同一组变量上进行重复操作,因此循环有称为迭代;递归是在不同变量组上进行重复操作,这些变量组属于递归函数的不同实例
      • 递归调用层次受栈空间的限制
      • 递归是由函数调用实现的,函数调用需要开销。(可用动态规划技术(dynamic programming)解决)
      • 分析递归算法的效率要考虑分解综合两个方面的代价
      • 循环实现的重复操作是一种归纳(递推)的过程,即从特殊情况到一般情况进行考虑;递归是一种演绎过程,是从一般情况到特殊情况设计的
    • 递归函数应用实例

    10、求两个正整数的最大公约数

    法一:

     

    int Function::gcd(int x,int y){
    
    int d ;
    
    d=(x<=y)?x:y;
    
    while(d>1){
    
    if(x%d==0&&y%d==0){
    
    break;
    
    }
    
    d--;
    
    }
    
    return d;
    
    }
    //法二:辗转相除法(欧几里得算法)
    int gcd(int x,int y){
    	return(y==0)?x:gcd(y,x%y);
    }
    

     

    11、汉诺塔问题

    void Function::hanoi(char x,char y,char z,int n){
    
    if(n==1){
    
    cout<<"1:"<<x<<"→"<<y<<endl;
    
    }else{
    
    hanoi(x,z,y,n-1);
    
    cout<<n<<":"<<x<<"→"<<y<<endl;
    
    hanoi(z,y,x,n-1);
    
    }
    
     
    
    }

    课后答案(仅供参考)

    1、将华氏度转为摄氏度

     

    void Test::test1(){

     

    double fahrenheit,degree;

    cout<<"请输入华氏度:"<<endl;

    cin>>fahrenheit;

    degree=5*(fahrenheit-32)/9;

    cout<<fahrenheit<<"华氏度对应的摄氏度为:"<<degree<<endl;

     

    }

     

     

    2、将24小时转为12小时

     

    void Test::test2(){

    int h1,m1;

    cout<<"输入时分:"<<endl;

    cin>>h1>>m1;

    if(h1<12){

    cout<<h1<<":"<<m1<<"am"<<endl;

    }else{

    cout<<h1-12<<":"<<m1<<"pm"<<endl;

    }

     

    }

     

     

    3、正向和逆向输出a~z

     

    voidTest::test3(){

     

    chara='a';

    charz='z';

    for(inti=0;i<=25;i++){

    if(i==25){

    cout<<a;

    }else{

    cout<<a<<",";

    }

    a++;

    }

    cout<<a<<endl;//{

    for(inti=0;i<=25;i++){

    if(i==25){

    cout<<z;

    }else{

    cout<<z<<",";

    }

    z--;

    }

    cout<<z<<endl;//`

     

     

    }

     

     

    4、判断输入的正整数的位数,并输出

     

    void Test::test4(){

     

    intn,count=1;

    cout<<"输入一个正整数:"<<endl;

    cin>>n;

    for(inti=10;i<n*10;i=i*10){

    int m=n/i;

    if(m>0){

    count++;

    }

    }

    cout<<n<<"是"<<count<<"位数"<<endl;

     

    }

     

     

    5、对输入的一个算术表达式(以字符#结尾),检查其圆括号的配对情况,输出配对、多左括号、多右括号

     

    voidTest::test5(){

     

    intleft=0,right=0;

    charc;

    cout<<"输入一个算术表达式:"<<endl;

    while(c!='#'){

    cin>>c;

    if(c=='{'){

    left++;

    }

    if(c=='}'){

    right++;

    }

    }

     

    if(left==right){

    cout<<"配对"<<endl;

    }elseif(left>right){

    cout<<"多左括号"<<endl;

    }elseif(left<right){

    cout<<"多右括号"<<endl;

    }

    }

     

     

    6、输入一个字符串(以字符#结尾),对其中的'>='计数

     

    voidTest::test6(){

     

    //输入一个字符串(以字符#结尾),对其中的'>='计数

    int count=0;

    char ch1='\0',ch2;

    cout<<"输入一串字符"<<endl;

    while(ch2!='#'){

    cin>>ch2;

    if(ch2=='='&&ch1=='>'){

    count++;

    }

    ch1=ch2;

    }

    //for(cin>>ch2;ch2!='#';cin>>ch2){

    //if(ch2=='='&&ch1=='>'){

    //count++;

    //}

    //ch1=ch2;

    //}

    cout<<">=个数:"<<count<<endl;

     

    }

     

     

    7、计算圆周率

     

    void Test::test8(){

    double sum=0;

    for(inti=1;(double)1/(2*i-1)>=1e-8;i++){

    int n=1;

    sum=sum+(double)1/(2*i-1)*n;

    n=n*-1;

    }

    cout<<"pi="<<setprecision(100)<<4*sum<<endl;

    }

     

    8、计算邮费

     

    voidTest::test7(){

     

    doubleweight,distance;

    cout<<"输入包裹重量和邮寄距离:"<<endl;

    cin>>weight>>distance;

    if(weight<=0){

    cout<<"输入错误"<<endl;

    }else if(weight>0&&weight<=15){

    cout<<"收费5元"<<endl;

    }else if(weight>15&&weight<=30){

    cout<<"收费9元"<<endl;

    }else if(weight>30&&weight<=45){

    cout<<"收费12元"<<endl;

    }else if(weight>45&&weight<=60){

    if(distance/1000<0){

    cout<<"收费14元"<<endl;

    }else{

    cout<<"收费"<<14+(distance/1000)*1<<"元"<<endl;

    }

    }else if(weight>60){

    if(distance/1000<0){

    cout<<"收费15元"<<endl;

    }else{

    cout<<"收费"<<15+(distance/1000)*2<<"元"<<endl;

    }

    }

     

    }

     

     

    9、找出所有三位数,它们等于它们的各个数字的立方和(水仙花数)

     

    voidTest::test9(){

     

    for(inti=0;i<10;++i){

    for(intj=0;j<10;++j){

    for(intk=0;k<10;++k){

    if(i*i*i+j*j*j+k*k*k==(i*100+j*10+k)&&((i*100+j*10+k)/100)>=1){

    cout<<(i*100+j*10+k)<<"";

    }

    }

    }

    }

     

     

    for(inti=100;i<1000;++i){

    inta=i/100;

    intb=i%100/10;

    intc=i%10;

    if(a*a*a+b*b*b+c*c*c==i){

    cout<<a<<""<<b<<""<<c<<""<<i<<endl;

    }

    }

     

     

    }

     

     

    10、求输入a和b的公约数

     

    void Test::test10(){

    int a,b,i=2,count=1;

    cout<<"输入ab的值"<<endl;

    cin>>a>>b;

    do{

    if(a%i==0&&b%i==0){

    count=i;

    }

    i++;

    }while(i<=a||i<=b);

    cout<<a<<"和"<<b<<"的最大公约数是:"<<count<<endl;

    }

     

     

    11、1、2、5元货币,购买价值为n元的物品有多少种支付方式

     

    voidTest::test11(){

     

    int n,w=1;

    cout<<"输入商品价格:"<<endl;

    cin>>n;

    for(int i=0;i<=n;++i){

    for(int j=0;j<=n/2;++j){

    for(int k=0;k<=n/5;++k){

    if(i+2*j+5*k==n){

    cout<<"第"<<w<<"种支付方式:"<<"一元:"<<i<<",二元:"<<j<<",五元:"<<k<<endl;

    w++;

    }

    }

     

    }

    }

    }

     

     

    12、判断输入整数是否为回文数

     

    void Test::test12(){

     

    int n,reversedInteger=0,remainder,originalInteger;

    cout<<"输入一个整数:"<<endl;

    cin>>n;

    originalInteger=n;

     

    //翻转

    while(n!=0)

    {

    remainder=n%10;

    reversedInteger=reversedInteger*10+remainder;

    n=n/10;

    cout<<n<<""<<remainder<<""<<reversedInteger<<endl;

    }

     

    //判断

    if(originalInteger==reversedInteger){

    cout<<originalInteger<<"是回文数"<<endl;

    }else{

    cout<<originalInteger<<"不是回文数"<<endl;

    }

    }

     

     

    13、输出十进制乘法表

     

    void Test::test13(){

     

    for(int i=1;i<10;++i){

    for(intj=1;j<=i;++j){

    cout<<i<<"*"<<j<<"="<<i*j<<"";

    }

    cout<<endl;

    }

     

    }

     


    https://github.com/zzq1996/ProgrameDesign

    参考:《程序设计教程:用C++语言编程》 陈家骏,郑滔

    展开全文
  • 本书全面讲述了数据结构与算法分析,即组织大量数据方法和对算法运行时间估计。 学习本书之前一定要对离散数学有一定了解。本书分别介绍了离散数学以及递归一些内容,然后讨论算法分析,主要包括表、栈、...
  • 算法与数据结构的区别:数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法程序=数据结构+算法总结:算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题的载体...

    一.数据结构基础

    1.数据结构概念

    就是一组数据在内存中的存储形式,也是对基本数据类型的一次封装

    也是数据对象中数据元素之间的关系。

    算法与数据结构的区别:

    数据结构只是静态的描述了数据元素之间的关系

    高效的程序需要在数据结构的基础上设计和选择算法

    程序=数据结构+算法

    总结:算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题的载体。

    2.抽象数据类型(ADT)

    就是将数据类型和数据类型上的运算捆在一起,进行封装,相当于类

    3.算法效率的衡量

    实现算法程序的执行时间可以反映出算法的效率

    但是单纯依靠运行的时间来比较算法的优劣不一定是客观准确的

    时间复杂度:

    反应算法在时间上的效率

    我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位,算法对于不同的机器环境而言,确切的单位时间是不同的,但是对于算法进行多少个基本操作在规模数量级上是相同的,因此可以忽略机器环境的影响客观的反应算法的时间效率。

    “大O记法”表示算法的时间效率:

    计算算法的基本操作的执行次数,为g(n),使得算法处理规模为n的问题示例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐进时间复杂度,简称时间复杂度,记为T(n)。

    理解“大O法”:对于算法的基本操作的执行次数,不用计算的太细致,最重要的是数量级和趋势,这个基本操作数量的规模函数中一些常量因子可以忽略不计。例如:

     和 

    属于同一个数量级,他们的时间复杂度都是

    级。

    最坏时间复杂度(主要关注):

    算法完成工作最多需要多少基本操作

    平均时间复杂度(比较全面):

    算法完成工作平均需要多少基本操作

    时间复杂度的几条基本计算规则:

    (1)基本操作,只有常数项。认为时间复杂度为O(1)

    (2)顺序结构,时间复杂度加法计算

    (3)循环结构,时间复杂度乘法计算

    (4)分支结构,时间复杂度取最大值

    (5)判断一个算法的效率时,往往只需要关注数量的最高次项,其他可以忽略。

    (6)没有特殊说明的情况下,分析的都是最坏时间复杂度

    list内置操作的时间复杂度:

    dict内置操作的时间复杂度:

    常见的时间复杂度之间的关系:

    所消耗的时间的大小:

    O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

    展开全文
  • 这三章中,读者也将对算法复杂度各种分析方法有所了解。 第八、九和十章论述重点完全转向算法。第八章对此前各章中陆续介绍过排序算法作了归 纳与分类,着重介绍了归并排序算法与快速排序算法,并给出了此类...
  • 书中内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书把算法分析与C++程序开发有机地结合起来,深入分析每种算法,...
  • 通过C程序的实现,着重阐述了抽象数据类型的概念,并对算法的效率、性能和运行时间进行了分析。 全书特点如下: ●专用一章来讨论算法设计技巧,包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法 ...
  • 通过C程序的实现,着重阐述了抽象数据类型的概念,并对算法的效率、性能和运行时间进行了分析。 《数据结构与算法分析:C语言描述》特色:着重讨论了算法设计技巧,包括贪婪算法、分治算法、动态规划、随机化算法...
  • 进化算法包括遗传算法、进化程序设计、进化规划和进化策略等等,进化算法的基本框架还是简单遗传算法所描述的框架,但在进化的方式上有较大的差异,选择、交叉、变异、种群控制等有很多变化,进化算法的大致框图可...
  • 数据结构与算法分析:C语言描述 全书特点如下:1.专用一章来讨论算法设计技巧,包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法;2.介绍了当前流行论题和新数据结构,如斐波那契堆、斜堆、二项队列、...
  • 内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。 编辑推荐 《数据结构与算法分析C++描述》(第3版)适合作为计算机...
  • 第2章算法一程序的灵魂 1 教学要求要求学生了解...3 教学内容算法的特性用自然语言或伪代码方式书写简单算法用流程图和 N-S图表小算法 一个程序应包括两个方面的内容 ?操作的描述算法(algorithm) ?数据的描述数据
  • 算法

    2019-11-25 23:24:53
    一个程序主要应该包括两方面内容:一个是数据组织的描述,另一个则是程序操作的描述数据组织的描述称为数据结构,而程序操作的描述称为算法。因此有这样一个公式:数据结构+算法=程序。对于面向对象程序设计...

    一个程序主要应该包括两方面内容:一个是对数据组织的描述,另一个则是对程序操作的描述。对数据组织的描述称为数据结构,而对程序操作的描述称为算法。因此有这样一个公式:数据结构+算法=程序。对于面向对象程序设计,强调的是数据结构,而对于面向过程程序设计,如C. Pascal. FORTRAN等语言,主要关注的是算法。

     

    算法:解决一个问题的完整步骤描述。

    五个特征:有穷、正确、可行、输入、输出。

    三种基本结构:顺序、选择、循环

    流程图:普通流程图    ;  N-S流程图

     

     

    下面介绍排序算法:

    为什么介绍排序算法呢?因为 排序是数据处理中的一种重要运算。在当今计算机系统中,花费在数据排序的时间占用了一部分系统运行的时间,所以研究并采用好的排序算法,能够提高工作效率是很重要的。

    //选择排序
    #include<stdio.h>
    int main()
    {
    	int a[10];
    	int i,j,k,m;
    	printf("10 numbers:\n");
    	for(i=0;i<10;i++)
    	{
    		scanf("%d",&a[i]);
    	}
    	for(i=0;i<9;i++)
    	{
    		k=i;
    		for(j=i+1;j<10;j++)
    			if(a[k]>a[j])
    				k=j;
    			if(k!=i)
    			{
    				m=a[i];
    				a[i]=a[k];
    				a[k]=m;
    			}
    	}
    	printf("The sorted array is :  by the chosen method .\n  ");
    	for(i=0;i<10;i++)
    	{
    		printf("%d  ",a[i]);
    	}
    	printf("\n");
     } 
    //9 4 3 34 32 4 38 98 0 99

     

    //堆排序
    #include<stdio.h>
    #define LENGTH 20
    
     递归方式构建大根堆(len是arr的长度,index是第一个非叶子节点的下标)
    void adjust(int arr[],int len,int index)
    {
    	int left = 2*index + 1; // index的左子节点下表 
    	int right = 2*index + 2;// index的右子节点下标 
    	int temp;
    	int maxIdx=index;
    	if(left<len&&arr[left]>arr[maxIdx]) maxIdx=left;
    	if(right<len&&arr[right]>arr[maxIdx])  maxIdx=right;
    	if(maxIdx!=index)
    	{
    		temp=arr[maxIdx];
    		arr[maxIdx]=arr[index];
    		arr[index]=temp;
    		adjust(arr,len,maxIdx);
    	 } 
    }
    //堆排序
    void heapSort(int arr[],int size)
    
    {
    	int i,temp;
    	//构建大根堆(从最后一个非叶子节点向上) 
    	for(i=size/2-1;i>=0;i--)
    	{
    		adjust(arr,size,i);
    	}
    	printf("the max heap:\n");
    	for(i=0;i<size;i++)
    	{
    		printf("%d  ",arr[i]);	
    	} 
    	printf("\n");
    	//调整大根堆
    	for(i=size-1;i>=1;i--)
    	{
    		temp=arr[i];
    		arr[i]=arr[0]; // 将当前最大的放置到数组末尾
    		arr[0]=temp;
    		adjust(arr,i,0);// 将未完成排序的部分继续进行堆排序
    	 } 
     } 
     main()
     {
     	int b[LENGTH];
     	int i;
     	for(i=0;i<LENGTH;i++)
     	{
     		scanf("%d ",&b[i]);
    	 }
    	 printf("\n");
    	 heapSort(b,LENGTH);
    	 for(i=0;i<LENGTH;i++)
    	 {
    	 	printf("%d  ",b[i]);
    	 }
    	 return 0;
    	 
     }

     

    8 9 0 2 3 4 223 4 3 78 6767 9889 78 67 56 45 34 23 21 213 99

    //冒泡排序
    #include<stdio.h>
    main()
    {
    	int a[10]; 
    	int i,j,k;
    	printf("10 numbers:\n");
    	for(i=0;i<10;i++)
    	{
    		scanf("%d",&a[i]);
    	}
    	for(i=0;i<9;i++)//十个数进行九趟排序 
    	{
    		for(j=0;j<9-i;j++)
    		{
    			if(a[j]>a[j+1])
    			{
    				k=a[j];
    				a[j]=a[j+1];
    				a[j+1]=k;
    			}
    		}
    	 }
    	 printf("The sorted array is : by bubble.");
    	for(i=0;i<10;i++)
    	{
    		printf("%d  ",a[i]);
    	}
    	printf("\n"); 
     } 

    //quicksort
    //对冒泡的改进 
    #include<stdio.h>
    #define N 10000
    #include<time.h>
    main()
    {	
    	clock_t begin,end;
    	double cost;
    	int p(int a[],int low,int high);
    	void q(int a[],int low,int high); 
    	int a[N];
    	int i;
    	//printf("please input 10 numbers.\n");
    	int j=1000;
    	begin=clock();
    	for(i=0;i<N;i++)
    	{
    	//	scanf("%d",&a[i]);
    	a[i]=j--;
    	}
    	
    	q(a,0,N-1);
    	end=clock();
    	cost=(double)(end-begin);
    	printf("The sorted array is :  by quicksort method .\n  ");
    	for(i=0;i<N;i++)
    	{
    		printf("%d  ",a[i]);
    	}
    	printf("The cost is: %lf\n",cost); 
    } 
    int p(int a[],int low,int high)
    {
    	int key=a[low],p;
    	while(low<high)
    	{
    		while(low<high&&a[high]>=key)
    		{
    			--high;
    		}
    		p=a[low];
    		a[low]=a[high];
    		a[high]=p;
    		while(low<high&&a[low]<=key)
    		{
    			++low;
    		}
    		p=a[high];
    		a[high]=a[low];
    		a[low]=p;
    	}
    	a[low]=key;
    	return low;
    }
    void q(int a[],int low,int high)
    {
    	int j;
    	if(low<high)
    	{
    		j=p(a,low,high);
    		q(a,low,j-1);
    		q(a,j+1,high);
    	}
    }

     

     

     

    //quicksort
    //对冒泡的改进 
    #include<stdio.h>
    #define N 5000
    #include<time.h>
    main()
    {	
    	clock_t begin,end;
    	double cost;
    	int p(int a[],int low,int high);
    	void q(int a[],int low,int high); 
    	int a[N];
    	int i;
    	//printf("please input 10 numbers.\n");
    	int j=1000;
    	begin=clock();
    	for(i=0;i<N;i++)
    	{
    	//	scanf("%d",&a[i]);
    	a[i]=j--;
    	}
    	
    	q(a,0,N-1);
    	end=clock();
    	cost=(double)(end-begin);
    	printf("The sorted array is :  by quicksort method .\n  ");
    	for(i=0;i<N;i++)
    	{
    		printf("%d  ",a[i]);
    	}
    	printf("\nThe cost is: %lf\n",cost); 
    } 
    int p(int a[],int low,int high)
    {
    	int key=a[low],p;
    	while(low<high)
    	{
    		while(low<high&&a[high]>=key)
    		{
    			--high;
    		}
    		p=a[low];
    		a[low]=a[high];
    		a[high]=p;
    		while(low<high&&a[low]<=key)
    		{
    			++low;
    		}
    		p=a[high];
    		a[high]=a[low];
    		a[low]=p;
    	}
    	a[low]=key;
    	return low;
    }
    void q(int a[],int low,int high)
    {
    	int j;
    	if(low<high)
    	{
    		j=p(a,low,high);
    		q(a,low,j-1);
    		q(a,j+1,high);
    	}
    }

     

     

    OPENMP并行快排主要利用了OpenMP里面的#omp parallel sections将对两个子数组的快速排序函数用两个线程并行化执行,至于线程的创建和销毁我们不用管,只要告诉编译器哪里的代码需要并行执行就可以了,具体请看OpenMP资料。

    //quicksort
    //对冒泡的改进 
    #include<stdio.h>
    #include<time.h>
    #include "omp.h"
    #define N 5000
    #pragma warning(disable:4996)
    int main()
    {	
    	omp_set_num_threads(2);//----------------设置线程数为2,因为是双核的CPU
    	double  cost;
    	clock_t begin, end;
    	int p(int a[], int low, int high);
    	void q(int a[], int low, int high);
    	int a[N];
    	int b[N / 2];
    	int c[N / 2];
    	int d[N];
    	int j = 1000;
    
    	int i = 0,k = 0,m=0,n=0;
    #pragma omp parallel default(none) shared(a,d,N) private(i)//private(list)表示每个线程的变量都是局部的,shared()表示的变量被线程组中所有线程共享,default()定义缺省范围
    	{	//---这个for循环是并行的  
    #pragma omp for
    		for (i = 0; i < N; i++)
    	{
    		a[i] = j;
    		d[i] = j;
    		j--;
    	}
    	}
    	begin = clock();
    #pragma omp parallel default(none) shared(a,b,c,N/2) private(i)//---这个for循环是并行的  
    	{
    #pragma omp for
    		for (i = 0; i < N / 2; i++)
    		{
    			b[i] = a[i];
    			c[i] = a[i + N / 2];
    		}
    	}
    #pragma omp parallel default(none) shared(b,c,N/2)//private(i)------快速排序的并行region 
    	{
    #pragma omp parallel sections
    		{
    #pragma omp section
    			q(b, 0, N/2 - 1);
    			
    #pragma omp section
    			q(c, 0, N / 2 - 1);
    		}
    	}
    	for (; k < N; k++)//----------将D[]和E[]进行归并排序放入B[]里面  
    	{
    		if (m < N / 2 && n < N / 2)
    		{
    			if (b[n] <= c[m])
    			{
    				d[k] = b[n];
    				n++;
    			}
    			else
    			{
    				d[k] = c[m];
    				m++;
    			}
    		}
    		if (m == N / 2 || n == N / 2)
    		{
    			if (m == N / 2)
    				d[k] = c[m];
    			else
    				d[k] = b[n-1];
    			k += 1;
    			break;
    		}
    	}
    	if (n < N / 2)
    	{
    		int tem = N / 2 - n;
    		int pp = 0;
    		for (pp = 0; pp < tem; pp++)
    		{
    			d[k] = b[n];
    			n++;
    			k++;
    		}
    	}
    	else if (m < N / 2)
    	{
    		int tem = N / 2 - m;
    		int pp = 0;
    		for (pp = 0; pp < tem; pp++)
    		{
    			d[k] = c[m];
    			m++;
    			k++;
    		}
    	}
    	end = clock();
    	printf("The sorted array is :  by quicksort method .\n  ");
    	for (i = 0; i < N; i++)
    	{
    		printf("%d  ", d[i]);
    	}
    	cost = (double)(end - begin);
    	printf("\n并行时间为:%lf\n",cost);
    }
    int p(int a[], int low, int high)
    {
    	int key = a[low], p;
    	while (low < high)
    	{
    		while (low < high && a[high] >= key)
    		{
    			--high;
    		}
    		p = a[low];
    		a[low] = a[high];
    		a[high] = p;
    		while (low < high && a[low] <= key)
    		{
    			++low;
    		}
    		p = a[high];
    		a[high] = a[low];
    		a[low] = p;
    	}
    	a[low] = key;
    	return low;
    }
    void q(int a[], int low, int high)
    {
    	int j;
    	if (low < high)
    	{
    		j = p(a, low, high);
    		q(a, low, j - 1);
    		q(a, j + 1, high);
    	}
    }

     

     

     

     

     

     

    #include <iostream>
    using namespace std;
    #define LENGTH 20
    
    //直接插入排序:将第一个数据看做一个顺序表,将后面的数据一次插入表中
    void InsertSort(int a[], int n)  
    {  
    for(int i= 1; i<n; i++){  
         int j= i-1;   //表中最后一个数据
        int x = a[i];        //复制为哨兵,即存储待排序元素  
        while(j>=0 && x < a[j]){  //查找在有序表的插入位置  (遍历表)
            a[j+1] = a[j];  
            j--;         //元素后移  
        }  
        a[j+1] = x;      //插入到正确位置  
    }  
      
    } 
    
    int main()
    {
    
    int b[LENGTH];
    for(int i=0;i<LENGTH;i++){
        printf("%d ",b[i]);
    }
    
    cout<<"\n";
    InsertSort(b,LENGTH);
    for(int i=0;i<LENGTH;i++)
        cout<<b[i]<<" ";
    
    return 0;
    }

     

     

    基本思想是:希尔排序是在插入排序的基础上进行发展的,通过一个希尔增量先排序一定间隔的数据。待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
    平均时间复杂度:O(N^3/2)
    空间复杂度:O(1)
    稳定性:不稳定

    #include <iostream>
    using namespace std;
    #define LENGTH 20
    void shellsort(int a[],int n) {  
    for (int increment = n / 2; increment > 0; increment /= 2)
    {
        for (int i = increment; i < n; i++)
        {
            int insert_num = a[i], j;
            for (j = i - increment; j >= 0; j -= increment)
            {
                if (a[j] > insert_num)
                    a[j + increment] = a[j];
                else
                    break;
            }
            a[j + increment] = insert_num;
        }
    } 
    }  
    int main()
    {
    
    int b[LENGTH];
    for(int i=0;i<LENGTH;i++){
        printf("%d ",b[i]);
    }
    cout<<"\n";
    shellsort(b,LENGTH);
    for(int i=0;i<LENGTH;i++)
        cout<<b[i]<<" ";
    
    return 0;
    }

     

    展开全文
  • 通过C程序的实现,着重阐述了抽象数据类型的概念,并对算法的效率、性能和运行时间进行了分析。 全书特点如下: ●专用一章来讨论算法设计技巧,包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法 ●...
  • 通过C程序的实现,着重阐述了抽象数据类型的概念,并对算法的效率、性能和运行时间进行了分析。 《数据结构与算法分析:C语言描述》特色:着重讨论了算法设计技巧,包括贪婪算法、分治算法、动态规划、随机化算法以及...
  • 本书的目的就是有关算法的内容精心地组织,从而使得使用本书的同学以及实践者可以设计和分析全新的算法。 一本包含所有已发明的算法的书将会异常冗长。传统的算法书通常只很少的几个问题领域有深入的阐述。对于...
  • 数据结构与算法分析:C++语言描述(第四版)是数据结构和算法分析经典教材,书中使用主流程序设计语言C++作为具体实现语言。书中内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、...
  • 蓝桥杯:试题 算法训练 相邻数 Java 问题描述  给定n个不同整数,问这些数中有多少整数,它们值正好相差1。 输入格式  输入第一行包含一个整数n,表示给定整数... 值正好相差1对包括(2, 3), (6, 7)...
  • 2.4.5用伪代码表示算法 自学 2.4.6用计算机语言表示算法 自学 2.5结构化程序设计方法 自学 第2章 算法---程序的灵魂 一个程序主要包括以下两方面的信息 (1) 数据的描述在程序中要指定用到哪些数据以及这些数据的...
  • 而且已经作为指令系统一部分了,可见栈重要性,以前我链栈情有独钟,总觉得他永远不会出现栈满,而且实现起来比链栈复杂,很有成就感,但是今天看完算法分析这本书这一章才了解到,其实作为平常使用,...
  • C语言的算法

    2014-07-24 21:23:00
    什么是算法|算法的概念  一个程序应包括数据的描述:在程序中要指定数据的类型和数据的组织形式,即数据结构(data structure)。 操作的描述:即操作步骤,也就是算法(algorithm)。  Nikiklaus ...
  • 算法这些结构中数据进行各种处理,例如排序。 例子:一条人事档案记录描述了一位真实忍信息,一条存活纪录描述了一个真实存在汽车部件活着杂货店里一种商品,一条财务交易描述了一笔交易信息。
  • 本书是国外数据结构与算法分析方面经典教材,使用卓越Java编程语言作为实现工具,讨论数据结构(组织大量数据方法)和算法分析(对算法运行时间估计)。 随着计算机速度不断增加和功能日益强大,人们对...
  • VB常用算法的介绍.pdf

    2020-08-02 11:59:14
    常用算法介绍 VB 算法 Algorithm 计算机解题的基本思想方法和步骤算法的描述要 解决一个问题或要完成一项任务所采取的方法和步骤的描述 包括需要什么数据 输入什么数据输出什么结果采用什么结构使用什么语句...
  • 算法的基础知识笔记

    2021-02-14 10:56:25
    算法是指解题方案准确而完整的描述。简而言之,算法是解决问题的操作步骤。算法不等于数学上的计算方法,也不等于程序。程序可以描述算法。 算法的基本特征如下:(1)可行性,步骤可以实现,执行结果达到预期...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,742
精华内容 696
关键字:

对算法的描述包括