投稿
  1. 高性能架构探索首页
  2. C/C++

常用算法集锦-C/C++

admin • • C/C++ • 阅读 131

0,读入：

  #include <iostream>
  #include <stdio.h>

1)不断读取数字类型，遇到分隔符(空格或者换行)作为一次读取
while (cin >> number){   //获取键盘输入的值赋值给变量number,将会一直测试输入流是否正常，如果输入正常,继续循环获取键盘值，如果输入流错误或达到文件末尾,循环终止.
        if (number==0){   //如果输入的是数字0
            cout << "0 input";
            return 0;
        }
        ...
 }

2)不断读取多行，每一行有四部分的字符串组成，每一部分由空格分割
while(scanf("%s %s %s %s",a[0],a[1],a[2],a[3])!=EOF){
    ...
}

3)不断读取多行，每一个只有一个数字，且第1个代表之后接着多少个/行数字，可以是多组数据连接的
while(cin >> count){
       for(int i=0; i<count; i++){
            cin >> inputArray[i];
       }      
}

 4)不断读取多行，每一行是包含任意字符(包括空格)的字符串
  char input[MAX_COUNT+1];
  while(gets(input)) {                  //c语言库函数,可以直接输入带空格的一行字符串,丢弃缓冲区中的换行符,自动自动加上字符串结束符
  while(cin.getline(input,10,'#'){     //c++专有，指定长度，指定结束符，即遇到#算一行结束, 自动填充字符串结束符'\0'
  while(cin.getline(input,10){         //c++专有，指定长度，结束符为缺省的为'\n', 自动填充字符串结束符'\0'
     ...
  }
 　　or
  string str;
  while(getline(cin, str)) {                   //c++专有，不指定长度，结束符为缺省的为'\n'，即换行符
   　　len=str.length();
  　　//char[] ch = str.toCharArray();         //有的编辑器不认识
  　　if(str[0]!='0' || str[1]!='x') break;    //可以不用转化成数组，直接索引访问
 　}

 

5)c语言的读取

(1)1个数字
scanf("%d", &a); //scanf需要一个&

(2)一串字符
scanf: 遇到空格会返回

char *p; 遇到空格不会返回
gets(p);

(3)根据输入的内容确定数组的长度
int *array;
array=(int*)malloc(n*sizeof(int))

(4)从文件中读取(未实测)
用法1: 从文件句柄中读取一个个字符到c上, 然后打印到屏幕中, 一旦操作系统返回错误-1, 则意味着文件读取结束
int c;
while ((c = fgetc(fp)) != EOF) {
putchar (c);
}

用法2: 使用feof来读取文件句柄, 只有确实读取到文件结尾, 才返回true
while (!feof(fp)) {
c = fgetc(fp);
　　...do something;...
}

 

注1：cin是遇到Space、Enter、Tab停止读取，即算作一次读取

           遇到整个文件的结束符，或者说在读取标准输入io的时候，ctrl+z  +   回车，则退出整个读取循环。

 注2:   除了表示文件结尾，EOF还可以表示标准输入的结尾， 比如getchar() != EOF

 

1,常用函数

#include <string.h>

len = strlen(input);

 

 

例1:计算24点

输入4张牌，输出一个算式，算式的结果为24点。 

1.运算只考虑加减乘除运算，没有阶乘等特殊运算符号，友情提醒，整数除法要当心； 
2.牌面2~10对应的权值为2~10, J、Q、K、A权值分别为为11、12、13、1； 
3.输出算式的运算顺序从左至右，不包含括号，如1+2+3*4的结果为24，如果存在多种算式都能计算得出24，只需输出一种即可，如果无法得出24，则输出“NONE”表示无解。
 
思路：整体思路是多种运算符号和多种运算数之间的组合，分两大模块
           首先将输入的四个数字做一个排序，得到一组排序后对该组数字进行试探计算，如果计算成功则不再继续进行排序；
            然后是试探计算，所谓试探的含义是：四个数字n1， n2， n3，n4，首先固定最后一个数，和他前面的运算符，比如
                                                                         首先假设  前置算式 + n4,  然后将 前置算式 作为一个新的输入递归计算；
                                                                          然后，如果计算到第0个数字还是不行，那么就 前置算式 - n4， 依次类推；
 　　　　　　　　　　　　　　　　　　　　　　　如果计算后是正确的，那么返回true，上层递归调用发现是true，则也直接停止计算和排序，返回 
 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>

using namespace std;
#define COUNT 4
#define EPS 1e-6

char fuhao[3];
int number[COUNT];
int newArray[COUNT];
bool find;

//2.因为这里面有double类型的数学计算，因此保险用这种方式判断两个数是否相同
bool iszero(double x){
    return fabs(x)<=EPS;
}

//第3步：计算a数组的前n个数字进行排列组合后能否得到值为expect，注意expect表示期望得到的值，是一个double类型
//      是一个递归调用，从后向前先固定一个运算符 + 最后一个运算数，然后知道自己希望前面几个运算数经过组合得到的值应该是多少,所以递归计算
bool caculate(int a[COUNT], int n, double expect){
    int index=n-1;
    bool isexpect; 
    if(index==0){
        if(iszero(a[index]-expect))return true;
        else return false;
    }
    fuhao[index-1]='+';
    isexpect=caculate(a,index,expect-a[index]);
    if(isexpect) return true;

    fuhao[index-1]='-';
    isexpect=caculate(a,index,expect+a[index]); 
    if(isexpect) return true;

    fuhao[index-1]='*';
    isexpect=caculate(a,index,expect/a[index]);
    if(isexpect) return true;

    fuhao[index-1]='/';
    isexpect=caculate(a,index,expect*a[index]);
    if(isexpect) return true;  
  
    return false;
}

char getOutChar(int i){
    char tmp;
    switch (i){
        case 11: tmp='J';break;
        case 12: tmp='Q';break;
        case 13: tmp='K';break;
        case 1: tmp='A';break;
        default: tmp=i+'0';
    }
    return tmp;
}
//第2步：对输入的数据进行组合排序，核心算法为：
//      利用一个循环，轮流做新组合的第1把交椅，固定第一把交椅后，
//                    再从剩下的数字中轮流做剩下交椅中的第一把交椅(递归)
//        但是这里需要注意的是，所谓剩下的数字不是"之后的数字"，而是"剩下的数字"，所以需要用一个数组来标识哪个数字已经坐上交椅了。
char used[COUNT];  //用来记录在组合排序的时候 是否已经算进来了 
bool permuteAndCaculate(int pos, const int n,const int r)
{
    int i;
    bool find=false;
    if(pos == r){   //如果已经是第r个元素了，则可打印r个元素的排列
        if(caculate(newArray,r,24)){
            for(i=0; i<r-1; i++){
                if(newArray[i]==10) cout << 10;
                else  cout << getOutChar(newArray[i]);
                cout << fuhao[i];
            }

            if(newArray[r-1]==10) cout <<10;  //单独打印,因为最后一个数字后面没有符号 else cout << getOutChar(newArray[i]);

            cout<<endl; 
            return true;
        }
        return false;
    }
    for (i=0; i<n; i++){
        if(!used[i]){
            newArray[pos]=number[i];
            used[i] = 1;
            /*递归搜索，得到后续元素 */
            find=permuteAndCaculate(pos+1,n,r);
            /*恢复递归前的值，目的是使以后该元素可作为后续元素使用*/
            used[i] = 0;
            if(find)  //如果在深层递归中已经找到了满足条件的。那么也不需要继续计算了 
                break;
        }
    }
    return find;
}

int main(){
    char a[COUNT][10];
    int result[COUNT];
    //while(scanf("%s %s %s %s %s",a[0],a[1],a[2],a[3],a[4])!=EOF){
    while(scanf("%s %s %s %s",a[0],a[1],a[2],a[3])!=EOF){
        bool iserror=false;   //注意一定在这里重置一下，否则上一轮的测试可能将他初始值变更

        //第1步：check valid
        for(int i=0; i<COUNT; i++){
            //if(strcmp(a[i],"joker")==0 || strcmp(a[i],"JOKER")==0){   //注意这里面假设真正的扑克牌，即大小王固定，且不会出现数字0等怪异字符
            if(strlen(a[i])>2){  //joker or JOKER                   //如果保险起见，还是应该这样的判断逻辑才对
                iserror=true;
                break;   //最好不要直接return,for next scan
            }
            else if(strlen(a[i])==2&&a[i][0]=='1'&&a[i][1]=='0') number[i]=10;
            else if(strlen(a[i])==1){
                if(a[i][0]>'0'&&a[i][0]<='9') number[i]=a[i][0]-'0';
                else{
                    switch(a[i][0]){
                    case 'J':number[i]=11; break;
                    case 'Q':number[i]=12; break;
                    case 'K':number[i]=13; break;
                    case 'A':number[i]=1; break;
                    default: 
                        iserror=true;
                        break;
                    }
                    if(iserror) break;
                }
            }
            else{
                iserror=true;
                break;
            }
        }
        
　　　　　//第2,3步:计算
        if(iserror)
            cout <<"ERROR"<<endl;
        else{
             if(!permuteAndCaculate(0,COUNT,COUNT))
                cout << "NONE"<<endl;    //结束换行符很重要 
        }
    }
    return 0;
}

 

递归专场

#include <iostream>

using namespace std;

#define M 5
#define N 5
char data[M][N]={
    {'a','b','c','c','e'},
    {'f','g','a','e','d'},
    {'s','a','p','l','e'},
    {'y','y','u','k','w'},
    {'k','j','m','z','q'}
};


int main(){
    int i,j;

    //cout <<"输出：" << endl;     
    for(i=0;i<M;i++){
        for(j=0;j<N;j++)
            cout << data[i][j]<<' ';
        cout << endl;
    }
    return 0;
}

 

例2：计算数独

玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复。

核心算法：如果该空格是该行或者该列的唯一一个空格，则直接固定；否则先固定一个值递归计算剩下是否合法；

                  剩下的是否合法也是使用这样的方式，如果递归发现剩下的确定不合法则返回到上层，换成下一个值。

　　　　　所谓合法：不能随便固定一个值，即不能是和其他格中相同的数字，算法是：

                             遍历当前行/列/小框框，看看新放置的这个数字是否合法，即是否在这一行中已经存在了

                             按照上面的逻辑，一共是9宫格，又只有1-9的9个数字，所以一路下来，如果都能不重复的填进坑，则刚好

                  注意：这个由于是一个二维的检测，所以最好是向所有的编码成一维的。

#include <iostream>

using namespace std;

#define WEIDU 9
int num[WEIDU][WEIDU];

bool check(int value, int raw, int column){
    int i,j;    
    //raw and column
    for(i=0;i<WEIDU;i++){
        if(num[raw][i]==value) return false;  
        if(num[i][column]==value)  return false;
    }
    //box
    int start_raw=raw/3*3;
    int start_col=column/3*3;
    for(i=start_raw; i<start_raw+3;i++)
        for(j=start_col; j<start_col+3;j++)
            if(num[i][j]==value)
                return false;

    return true; 
}

bool dfs(int raw, int column){
    int i,j;
    bool ok;
    for(int v=1; v<=9; v++){
        if(check(v,raw,column)){
            num[raw][column]=v;
            ok=true;
            for(i=0; i<WEIDU; i++){
                if(num[i][column]==0){
                    if(!dfs(i,column)){
                        ok=false;
                        num[raw][column]=0;
                        break;
                    }
                } 
            }
            if(ok==false) continue;

            ok=true; 
            for(j=0; j<WEIDU; j++){
                if(num[raw][j]==0){
                    if(!dfs(raw,j)){
                        num[raw][column]=0;
                        ok=false;
                        break;
                    }
                }      
            }
            if(ok==false) continue;
           
            return true;
        }   
    }
    //cout <<"have no valid value for:"<<raw<<column<<endl;
    return false;


}
int main(){
    int i,j;
    bool end=false;
    for(i=0;i<WEIDU;i++)
        for(j=0;j<WEIDU;j++)
            cin >> num[i][j];

             //为了测试用例de的bug 
　　for(i=0; i<WEIDU; i++){
        for(j=0; j<WEIDU; j++){
            if(num[i][j]==0){
                dfs(i,j);
                end=true;
                break;
            }   
        }
        if(end)
            break;
    }

    //cout <<"输出：" << endl;     
    for(i=0;i<WEIDU;i++){
        for(j=0;j<WEIDU;j++)
            cout << num[i][j]<<' ';
        cout << endl;
    }
    return 0;
}

原文链接: https://www.cnblogs.com/shuiguizi/p/12343951.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    常用算法集锦-C/C++

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/331178

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月1日 下午5:56
下一篇 2023年3月1日 下午5:56

相关推荐