數組求和算法系列

一直想寫一個數組求和算法系列博客，但由于自己算法能力有限，完成不了，只能完成其中簡單的部分，難的部分希望有園友愿意和我一起完成。在寫這篇博客的過程中借用了別人的思路，有的的確是要一定的算法和數據結構基礎，特別是對遞歸的理解，到現在為止我覺得我還沒有真正的理解遞歸。我一向不太喜歡廢話，我的博客要么是有關分析的，要么就是源碼

下面的代碼希望對你有所幫助：

1. 在排序數組中查找和為給定值的兩個數字,輸出一對

代碼

//在排序數組中查找和為給定值的兩個數字,輸出一對
void FineTwo(int*A,int size,int n)
    {
        if(n<1|| size<1)
        {
            return;
        }
        int beg=0;
        int end=size-1;
        while(beg<end)
        {
            if(A[beg]+A[end]==n)
            {
                cout<<A[beg]<<"\t"<<A[end]<<endl;
                break;
            }
            if(A[beg]+A[end]<n)
            {
                ++beg;
            }else 
            {
                --end;
            }
        }

2. 在排序數組中查找和為給定值的兩個數字,輸出所有對

代碼

//在排序數組中查找和為給定值的兩個數字,輸出所有對
void FineAll(int*A,int size,int n)
    {
        if(n<1|| size<1)
        {
            return;
        }
        int beg=0;
        int end=size-1;
        while(beg<end)
        {
            if(A[beg]+A[end]==n)
            {
                cout<<A[beg]<<"\t"<<A[end]<<endl;
                ++beg;
            }
            if(A[beg]+A[end]<n)
            {
                ++beg;
            }else 
            {
                --end;
            }
        }
    }

3. 輸出1~M中，所有連續的和等于N的數

代碼

//輸出1~M中，所有連續的和等于N的數
void FindContinueSequence(int size,int n)
    { 
        if(size<1|| n<1)
        {
            return;
        }
        int beg=1;
        int end=2;
        int sum=beg+end;
        while(beg<size) 
        {
            if(sum==n)
            {
                print(beg,end);
            }

            while(sum>n)
            {
                sum-=beg++;
                if(sum==n)
                {
                    print(beg,end);
                }
            }
            sum+=++end;
        }
    }

    void print(int beg,int end)
    {
        for(int i=beg;i<=end;i++)
        {
            cout<<i<<"\t";
        }
        cout<<endl<<endl;
    }

4. 輸出字符串的所有排列

代碼

//輸出字符串的所有排列
void Permutation(string a, int start)
    {
        int end=a.length()-1;
        if(start == end)
        {
           cout<<a<<endl;
        }else{
            staticchar tmp=NULL;//靜態變量的定義只執行一次，而非靜態變量在遞歸的過程中不停的構造和析構，當然它析構得比較晚
for(int i = start; i <= end; i++)
            {  
                tmp=a[start]; a[start]=a[i]; a[i]=tmp;
                Permutation(a, start+1);
                tmp=a[start]; a[start]=a[i]; a[i]=tmp;
            }
        }
    }

5. 輸出字符串的所有組合

代碼

//輸出字符串的所有組合
void combine(char* str)
    {
        if(str == NULL)
        {
            return;
        }

        int length = strlen(str);
        vector<char> res;
        for(int i =1; i <= length; ++ i)
        {
            combine(str, i, res);
        }
    }

    void combine(char* str, int num, vector<char>& res)
    {
        if(num==0)
        {
            vector<char>::iterator iter = res.begin();
            for(; iter < res.end(); ++ iter)
            {
                cout<<*iter<<"\t";
            }
            cout<<endl;
        }else{
            if(*str =='\0')
            {
                return;
            }

            res.push_back(*str);
            combine(str +1, num -1, res);
            res.pop_back();
            combine(str +1, num, res);
        }
    }

6. 找出排序數組中所有和等于給定數的所有序列

　　我本來的思路是想找出由最小的一組數的和等于給定的數，然后對這一組數進行組合，得出其他的一些序列，后來發現這個思路有缺陷，就放棄了，暫時還沒有想到其他的思路。

7. 找出由最小的一組數的和等于給定的數，又延伸延伸出另一個題目：在排序數組中，找出由個數最多的一組和等于給定數的序列。

我的錯誤代碼

//arr排序數組，bSize得出的序列元素個數，sum給定數，后來發現這個思路又是錯的
int* getBaseArr(int* arr,int& bSize,int sum)
        {
            int tmpSum=arr[0];
            int i=1;
            while(tmpSum<sum)
            {
                tmpSum+=arr[i++];
            }

            int k=0;
            if(tmpSum>sum)
            {
                k=tmpSum-sum;
                for(int j=0;j<i;j++)
                {
                    if(k!=arr[j])
                    {
                        continue;
                    }
                    k=j;
                    --i;
                    break;
                }
            }else{
                k=i;
            }

            int* a=newint[i];
            for(int j=0;j<i;j++)
            {
                if(j<k)
                {
                    a[j]=arr[j];
                }else
                {
                    a[j]=arr[j+1];
                }
            }
             
            bSize=i;
            return a;
        }

8. 在排序數組中，找出由個數最少的一組和等于給定數的序列。

6,7,8題，希望有興趣的園友可以做一下

作者：陳太漢

博客：http://www.rzrgm.cn/hlxs/

QQ：584917974

posted @ 2011-08-24 12:36 古文觀芷閱讀(7455) 評論(7) 收藏舉報

刷新頁面返回頂部

數組求和算法系列

數組求和算法系列

公告