设计一个算法在1、2、... 、9(顺序不能变)数字之间插入+或-或什么都不插入，使得计算结果总是100的程序，并输出所有可能性。例如1+2+34-5+67-8+9=100(回溯法)

本文主要是介绍设计一个算法在1、2、... 、9(顺序不能变)数字之间插入+或-或什么都不插入，使得计算结果总是100的程序，并输出所有可能性。例如1+2+34-5+67-8+9=100(回溯法)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include <stdio.h>
#include <string.h>
#define N 9
using namespace std;
void fun(char op[], int sum, int prevadd, int a[], int i);

void diapasolution(char op[], int a[]);



int main(){
    int a[N];
    char op[N];
    for(int i=0;i<N;i++){
        a[i]=i+1;
    }
    printf("求解结果\n");
    fun(op,a[0],a[0],a,1);      //插入位置从i开始

}

void fun(char op[], int sum, int prevadd, int a[], int i) {
    if(i==N){               //扫描完所有位置
        if(sum==100)        //找到一个解
            diapasolution(op,a);//输出解
        return;
    }
    op[i]='+';                              //位置i插入‘+’
    sum+=a[i];                              //计算结果
    fun(op,sum,a[i],a,i+1);               //继续处理下一个位置
    sum-=a[i];                              //回溯
    op[i]='-';                              //位置i 插入‘-’
    sum-=a[i];                              //计算结果
    fun(op,sum,-a[i],a,i+1);              //继续处理下一个位置
    sum+=a[i];                              //回溯
    op[i]=' ';                              //位置i插入空格
    sum-=prevadd;                           //先减去前面的元素值
    int temp;                               //计算新元素值
    if(prevadd>0)
        temp=prevadd*10+a[i];
    else
        temp=prevadd*10-a[i];
    sum+=temp;                             //计算合并结果
    fun(op,sum,temp,a,i+1);             //继续处理下一个位置
    sum-=temp;                             //回溯
    sum+=prevadd;
}

void diapasolution(char op[], int a[]) {
    printf("%d",a[0]);
    for(int j=1;j<N;j++){
        if(op[j]!=' ')
            printf("%c",op[j]);
        printf("%d",a[j]);
    }
    printf("=100\n");
}

这篇关于设计一个算法在1、2、... 、9(顺序不能变)数字之间插入+或-或什么都不插入，使得计算结果总是100的程序，并输出所有可能性。例如1+2+34-5+67-8+9=100(回溯法)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！