m0_51771971
m0_51771971
采纳率66.7%
2021-01-04 16:59

新手求助,一道算法题(木棒拼正方形)

5
已采纳

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

/*

描述

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

关于输入

第一行一个整数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;

}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

6条回答

  • weixin_42910064 泡视界 3月前

    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);不知我说的对不对

    点赞 评论 复制链接分享
  • m0_51771971 m0_51771971 3月前

    十分感谢🙏感觉犯了个很蠢的错误🤦‍♂️

    点赞 评论 复制链接分享
  • weixin_42910064 泡视界 3月前

    卡在了 while(arr[i]>length)    continue;

    点赞 评论 复制链接分享
  • m0_51771971 m0_51771971 3月前

    新手刚上路,经常意识不到逻辑错误,求指点

    点赞 评论 复制链接分享
  • m0_51771971 m0_51771971 3月前

    麻烦可以说的详细点吗

    点赞 评论 复制链接分享
  • qq_40693603 sinJack 3月前

    死循环了,好好看下你递归的逻辑

    点赞 评论 复制链接分享