【深搜】和為零

題目描述

請考慮一個由1到N（N=3, 4, 5 … 9）的數字組成的遞增數列：1 2 3 … N。現在請在數列中插入“+”表示加，或者“-”表示減，抑或是“ ”表示空白，來将每一對數字組合在一起（請不在第一個數字前插入符号）。計算該表達式的結果并注意你是否得到了和為零。請你寫一個程式找出所有産生和為零的長度為N的數列。

輸入

單獨的一行表示整數N (3 <= N <= 9)。

輸出

按照ASCII碼的順序，輸出所有在每對數字間插入“+”, “-”, 或 “ ”後能得到和為零的數列。(注意:就算兩個數字之間沒有插入符号也應該保留白格)

樣例輸入

樣例輸出

1+2-3+4-5-6+7

1+2-3-4+5+6-7

1-2 3+4+5+6+7

1-2 3-4 5+6 7

1-2+3+4-5+6-7

1-2-3-4-5+6+7

解題思路：

可以使用深搜，不斷枚舉三種符号 ‘+’ ‘-’ ’ ’ 三種情況，并驗證和為零。然後設定三個參數DFS（pos,sum,num），

pos指的是目前位置，sum為整個算式的和，num為目前數。

題解：

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

using namespace std;

char s[20]; 
int n;

void DFS(int pos,int sum,int num) 
//三個參數分别表示：目前位置，不含目前位置的和，目前位置上的數 
{
    int i;
    
    if(pos==n)
    {
        if(sum+num==0)
        {
            printf("%s\n",s);
        }
        return;
    }
    
    s[pos*2-1]=' ';  //搜尋‘ ’号
    
    if(num>0)
    {
        DFS(pos+1,sum,num*10+pos+1);
    }
    else
    {
        DFS(pos+1,sum,num*10-pos-1);
    }
    
    s[pos*2-1]='+';  //搜尋‘+’号
    DFS(pos+1,sum+num,pos+1);
    
    s[pos*2-1]='-';  //搜尋‘-’号
    DFS(pos+1,sum+num,-(pos+1));
}

int main()
{
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        s[i*2]=i+'1';
    }
    DFS(1,0,1);
    return 0;
}

運作結果：

【深搜】和為零