hdu1015 —— 回溯

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1015

因为之前看了下刘汝佳的《算法入门经典》，就用类似打印全排列，八皇后的方法做。本以为不难，结果却被两个细节搞了很久。1.在递归函数的出口没有把sum设为原来的值，结果导致当不符合条件时sum一直加下去。 2.pow（）函数的返回值是浮点型，而我一开始将sum和tg定为int类型，导致比较是否相等时出现了误差（其实自己不太清楚这方面的东西）

下面是代码：

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<stdlib.h>

double tg;

int len;

char a[20],b[20];//a存输入的字母，从0开始存。 b存目标字母，从1开始。

int cmp(const void*a, const void*b)

{

    return *(char*)b-*(char*)a;

}

int solve(double sum,int n)

{

    if(n==6)

    {

        if(sum==tg)

            return 1;

        else

            return 0;

    }

    for(int i = 0;i<len; i++)

    {

        int j;

        for(j = 1;j<n;j++)//寻找是否与已存的字母重复

        if(a[i]==b[j]) break;

        if(j==n)//若不重复，则存入现在的b[n]中

        {

            double sum1 = sum;//记录原先的sum值，若不符合条件，则将其值还原

            b[n] = a[i];

            if(n%2)

                sum += pow(b[n]-64,n);

            else

                sum -= pow(b[n]-64,n);

            if(solve(sum,n+1))

                return 1;

            sum = sum1;//在递归的出口将sum还原为之前的值，这样才不会妨碍下一个字母的操作

        }

    }

    return 0;

}

int main()

{

    while(scanf("%lf %s",&tg,a)==2 && (tg || strcmp(a,"END")))

    {

        len = strlen(a);

        qsort(a,len,sizeof(a[0]),cmp);//将输入的字母排序，以便最大字典序输出

        if(solve(0,1))

            puts(b+1);//由于b从1开始存，所以输入的地址要加一个单位

        else

            puts("no solution");

    }

    return 0;

}

巴特西

hdu1015 —— 回溯

最新文章

热门文章