😄算法太菜。

Algorithm——递归思想和树

Question

借助一简单的算法程序设计题来熟悉递归思想简单Tree.

题面为:
给一个正整数n,求有多少种非0的整数组合之和等于n.
例如:    2=1+1
      3=1+1+1
      3=1+2

Idea

通过树分支的方式来寻找答案,树的根root=1,然后逐渐循环获取每个分支之和为n,小于n则继续扩展。

#include<iostream>
#include<algorithm> 
#include<vector>
#include<set>
using namespace std;

int flag=0;
vector<string> tree;

int di_gui(int head,int result,string treeone="1"){

    for(int i=1;i<=result-head;++i){
        if(i+head<result){
            string treetmp = treeone;
            treetmp+=to_string(i);
            di_gui(i+head,result,treetmp);

            //cout<<"dian"<<endl;
        }
        else{
            string treetmp2 = treeone;
            treetmp2+=to_string(i);
            tree.push_back(treetmp2);
            flag++;
            //cout<<flag<<endl;
        }
    }

}

string sort_string(string it){
    char arrchr[it.size()];
    string tmp ="";
    for(int i=0;i<it.size();++i){
        arrchr[i] = it.at(i);
    }
    sort(&arrchr[0],&arrchr[it.size()]);
    for(int i=0;i<it.size();++i){
        tmp += arrchr[i];
    }
    return tmp;
}

set<string> get_set(vector<string> atree){
    set<string> tmp;

    for(int i=0;i<atree.size();++i){
        tmp.insert(sort_string(atree.at(i)));
    }
    return tmp;
}

int main(){
    int num;
    int head;
    cin>>num;
    di_gui(1,num);
    cout<<flag<<endl;
    //去重处理 
    set<string> result = get_set(tree);
    for(auto it=result.begin();it!=result.end();++it){
        cout<<*it<<endl;
    }
//    for(int i=0;i<tree.size();++i){
//        cout<<tree.at(i)<<endl;
//    }


}

可以看到flag变量对应的就是Tree的分支总数,而题目要求的是没有重复组合的结果,在树的分支中存在重复的节点,例如我们要获得n=5的结果,那么1-3-11-1-3两个分支就产生了重复,此时对树的分支进行结点排序,然后通过集合去重,这时得到的才是真正的结果。

如果di_gui不用全局变量flag的话,可以把flag放入方法中:

int di_gui(int head,int result,string treeone="1"){
    int flag=0;
    for(int i=1;i<=result-head;++i){
        if(i+head<result){
            string treetmp = treeone;
            treetmp+=to_string(i);
            flag+=di_gui(i+head,result,treetmp);

            //cout<<"dian"<<endl;
        }
        else{
            string treetmp2 = treeone;
            treetmp2+=to_string(i);
            tree.push_back(treetmp2);
            flag++;
            //cout<<flag<<endl;
        }
    }
    return flag;

}

扩展

Python版固定长度的字符串排列组合:

#coding:utf-8

import hashlib

def perm(s=''):
    # 这里是递归函数的出口,为什么呢,因为这里表示:一个长度为1的字符串,它的排列组合就是它自己。
    if len(s)<=1:
        return [s]
    sl=[] #保存字符串的所有可能排列组合
    for i in range(len(s)):  #这个循环,对应 解题思路1)确定字符串的第一个字母是谁,有n种可能(n为字符串s的长度
        for j in perm(s[0:i]+s[i+1:]): #这个循环,对应 解题思路2)进入递归,s[0:i]+s[i+1:]的意思就是把s中的s[i]给去掉
            sl.append(s[i]+j) # 对应 解题思路2)问题就从“返回字符串中的字母排列组合” **变成了** “返回 第一个字母+除去第一个字母外的字符串的排列组合”
    return sl



def sha1(key):
    hash = hashlib.sha1()
    hash.update(str(key).encode('utf-8'))
    return hash.hexdigest()

if __name__ == '__main__':
    # dict0 = '12eshcn'
    # dict1 = '!2eshcn'
    # dict2 = '!@eshcn'
    # dict3 = '1@eshcn'
    dicts = ''#要排列组合的字符
    perm_nums=perm(dicts)
    print(len(perm_nums))
    # for key in perm_nums:
    #      flag = "flag{%s}"%key
    #      if str(sha1(flag)) == "e6079c5ce56e781a50f4bf853cdb5302e0d8f054":
    #          print(flag)

同样是递归+Tree的方法获取到结果。