新手求助，一道算法题（木棒拼正方形）

Question

调试的时候卡在一个地方突然动不了也不知道哪里有问题，求大神解答

/*

描述

有一些小木棒，请问能否用这些木棒拼出一个正方形？

关于输入

第一行一个整数c，表示下面有c组数据。

每组数据的第一行是一个整数m（4≤m≤20），表示木棒的数目，接下来m个数，表示木棒的长度。

关于输出

对每一组数据输出一行yes或no，表示能否使用全部的木棒拼出一个正方形。

*/

#include<stdio.h>

int suc=0;

void sort(int i,int j,int*arr)

{

    if(i>=j) return;

    int p1=i,p2=j;

    int a=arr[i];

    while(p1<p2)

    {

        while(arr[p2]>=a&&p1!=p2) p2--;

        arr[p1]=arr[p2];

        while(arr[p1]<=a&&p1!=p2) p1++;

        arr[p2]=arr[p1];

    }

    arr[p1]=a;

    sort(i,p1-1,arr);

    sort(p1+1,j,arr);

 

    return;

}

 

void ping(int length,int arr[],int m,int be_used[])//采用回溯的思想进行遍历，从第m根开始；length表示尚未拼接的长度

{                                                      //suc用于反馈是否拼接成功

    

    for(int i=m;i>=1;i--)

    {

        if((arr[i]==length)&&(be_used[i]==0))

        {   be_used[i]=1;   suc=1;  return;   }//成功

 

        if((arr[i]<length)&&be_used[i]==0)

        {

            be_used[i]=1;

            ping(length-arr[i],arr,m,be_used);

            if(suc==1)  return;

            else    be_used[i]=0;

        }

 

        while(arr[i]>length)    continue;

        

    }

   

    return;

}

 

int main(void)

{

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        if(i!=1)    printf("\n");

        int m,length,sum=0;

        scanf("%d",&m);

        int arr[21]={0};

        for(int j=1;j<=m;j++)

            scanf("%d",&arr[j]);

        sort(1,m,arr);

 

        

        for(int j=1;j<=m;j++)

            sum+=arr[j];

        if(sum%4!=0)

        {

            printf("no");

            continue;

        }

        else length=sum/4;

        if(arr[m]>length)

        {   printf("no");   continue;}

 

        int be_used[22]={0};//1代表木棒被使用

        for(int j=1;j<=4;j++)

        {

            suc=0;

            ping(length,arr,m,be_used);

            if(suc==0)  break;

        }

        if(suc==0)  printf("no");

        else printf("yes");

    }

 

    return 0;

}

Answer 1

while(arr[i]>length)    continue;

你这一句会导致在递归的时候，while为真，一直循环在continue这一句。

其实你算法想做的就是当arr[i]>length的时候继续for循环就行了

所以直接删了while(arr[i]>length)    continue;这一句就行了。

 

其次因为你这个arr数组是排序好的，因此在ping函数执行过程中，如果要进行递归，则表明之前判断过的长度已经不需要了，

因此我认为你的递归ping(length - arr[i], arr, m, be_used);，可以改写为ping(length - arr[i], arr, i, be_used);不知我说的对不对