搜索
编程论坛 → 开发语言 → 『 C语言论坛 』 → 向大神们请教个问题，求看我这个代码哪里错了。
标题：向大神们请教个问题，求看我这个代码哪里错了。
只看楼主
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 11 楼
 得分:10 
或者可以试试这个~感觉这个更像二叉树的遍历输出路径状态~

程序代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 10

typedef struct Array
{
    int data;
    unsigned visit;
}Array;

void input(Array* arr[] ,size_t len);
void print(Array* arr[] ,size_t len);

void fun(Array* arr[],size_t deep,size_t len);

void freeArr(Array* arr[],size_t len);

int main( void )
{
   Array* arr[N];
   int m=5;
  
   memset(arr,0,sizeof (arr));
   
   input(arr,m);
   
   fun(arr,0,m);
   
   freeArr(arr,m);
   
    return 0;
}

void input(Array* arr[],size_t len)
{
    size_t i;
    
    if (len>N)
        exit(0);
    
        
    for (i=0;i!=len;++i)
    {
        arr[i]=(Array* )malloc(sizeof (*arr[0]));
        
        if (arr[i]==NULL||!scanf("%d",&arr[i]->data))
            exit(0);
    }
}

void print(Array* arr[],size_t len)
{
        size_t i;
        
        for (i=0;i!=len;++i)
            if (arr[i]->visit)
                printf("%-4d",arr[i]->data);
                
       puts("");
}

void fun(Array* arr[],size_t deep,size_t len)
{
    if (deep==len)
    {
            print(arr,len);
            return ;
    }
     
    arr[deep]->visit=1;
           
    fun(arr,deep+1,len);
    
    arr[deep]->visit=0;
    
    fun(arr,deep+1,len);
    
}

void freeArr(Array* arr[],size_t len)
{
    size_t i;
    
    for (i=0;i!=len;++i)
        if (arr[i]!=NULL)
        {
            free(arr[i]);
            arr[i]=NULL;
        }
}


[此贴子已经被作者于2017-11-19 00:23编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-11-18 22:56
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 12 楼
 得分:5 
送多一个解题思路给你~

程序代码：
#include<stdio.h>
#include<stdlib.h>

#define N 5

int main( void )
{
    unsigned i;
    unsigned j;
    
    int arr[N];
    
    for (i=0;i!=N;++i)
        if (!scanf("%d",&arr[i]))
            exit(0);
    
    for (i=0;i!=1<<N;++i)
        for (j=N-1;j!=-2;--j)
            if (i>>j&1||j==-1)
                printf(j!=-1?"%-4d":"\n",arr[j]);
            
    return 0;
}

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-11-18 23:09
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 13 楼
 得分:5 
太久没练变量类型了~再来一个数组指针的~

程序代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define N 10

typedef struct Array
{
    int data;
    unsigned visit;
}Array;

Array(*input(Array (*arr)[],size_t len))[];
void print(Array (*arr)[] ,size_t len);

void fun(Array (*arr)[],size_t deep,size_t len);

void freeArr(Array (*arr)[],size_t len);

int main( void )
{
   Array (*arr)[N]=NULL;
   size_t m=5;
   
   arr=input(arr,m);
   
   fun(arr,0,m);
   
   freeArr(arr,m);
   
    return 0;
}

Array(*input(Array (*arr)[N],size_t len))[N]
{
    size_t i;
    
    if (len>N)
        exit(0);
    
     arr=(Array(*)[N])calloc(N,sizeof (Array));  
     memset(arr,0,N*sizeof (Array));
     
     if (arr==NULL)
         return 0;
         
    for (i=0;i!=len;++i)
        if (!scanf("%d",&arr[i]->data))
            exit(0);
    
    return arr;
}

void print(Array (*arr)[N],size_t len)
{
        size_t i;
        
        for (i=0;i!=len;++i)
            if (arr[i]->visit)
                printf("%-4d",arr[i]->data);
                
       puts("");
}

void fun(Array (*arr)[N],size_t deep,size_t len)
{
    if (deep==len)
    {
            print(arr,len);
            return ;
    }
     
    arr[deep]->visit=1;
           
    fun(arr,deep+1,len);
    
    arr[deep]->visit=0;
    
    fun(arr,deep+1,len);
    
}

void freeArr(Array (*arr)[N],size_t len)
{
    free(arr);
    arr=NULL;
}


[此贴子已经被作者于2017-11-19 00:51编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-11-19 00:24
Tic_Kurt
Rank: 1
等　级：新手上路
帖　子：6
专家分：0
注　册：2017-11-18
第 14 楼
 得分:0 
回复 10楼 九转星河
谢谢大佬，这两天没看论坛，结果今天一上来才看见大佬写的代码，实在感动，我先看看~
2017-11-23 23:19
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 15 楼
 得分:0 
自己弄了个DP动态规划出来,这个可以实现啦~

程序代码：
#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#include<string.h>

int Comp(const void* p1,const void* p2);

void Input(size_t** a,size_t** k,size_t* n,size_t* m);

void Fun(size_t a[],size_t k[],size_t n,size_t m);

void Output(size_t a[],size_t k[],size_t m);

int main( void )
{
    size_t* a=NULL;
    size_t* k=NULL;
    size_t n=0;
    size_t m=0;

    Input(&a,&k,&n,&m);

    Fun(a,k,n,m);
    
    Output(a,k,m);

    free(a);
    free(k);

    return 0;
}

int Comp(const void* p1,const void* p2)
{
    if (*(size_t*)p1>*(size_t*)p2)
        return 1;
    else if (*(size_t*)p1<*(size_t*)p2)
        return -1;

    return 0;
}

void Input(size_t** a,size_t** k,size_t* n,size_t* m)
{
    size_t i;

    puts("请输入元素个数和所求定值和:");

    if (scanf("%u%u",(unsigned* )n,(unsigned* )m)!=2)
        exit(0);
  
    *a=malloc(*n*sizeof(**a));

    if (*a==NULL)
    exit(0);

    memset(*a,0,*n*sizeof(**a));

    *k=malloc((*m+1)*sizeof(**k));

    if (*k==NULL)
    exit(0);

    memset(*k,-1,(*m+1)*sizeof(**k));

    printf("请输入%u个元素:\n",*(unsigned* )n);

    for (i=0;i!=*n;++i)
        if (scanf("%u",(unsigned* )&((*a)[i]))!=1)
            exit(0);
}


void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;
    
    qsort(a,n,sizeof(*a),Comp);

    for (++m;i!=m;++i)
        for (j=0;a[j]<=i&&j<n;++j)
            if (i==a[j]||k[i-a[j]]<j)
            {
                k[i]=j;

                break;
            }
}

void Output(size_t a[],size_t k[],size_t m)
{
    size_t i=0;
    size_t j=0;

    for (++m;i!=m;++i)
        if (k[i]!=-1)
        {
            printf("%u=%u",(unsigned)i,(unsigned)a[k[i]]);

            for (j=i;j-=a[k[j]];)
                printf("+%u",(unsigned)a[k[j]]);

            puts("");
        }
}


[此贴子已经被作者于2017-12-20 13:11编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-12-16 17:56
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 16 楼
 得分:0 
还找到了另一个版本的另外两种类似的解法~

程序代码：
void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;
    
    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;

    for (i=0;i!=m;++i)
        for (j=k[i]+1;j&&j!=n&&i+a[j]<m;++j)
            if (j<k[i+a[j]])
                k[i+a[j]]=j;
}


第二种解法~
程序代码：
void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;
    
    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;

    for (i=0;i!=m;++i)
        for (j=n-1;j>k[i];--j)
            if (i+a[j]<m)
                k[i+a[j]]=j;
}


感觉这两种解法都可以作为背包问题的前身(感觉完全背包问题写法形式上比0-1背包还要简单一些)~

个人认为这里的第一种解法在背包容量不足的情况下剪枝叶效率会比第二个效率高些(但时间复杂度还是在同一个数量级别),不过第二个解法的逻辑方法比较精妙一些~

算啦~突然有大神和我说就算是顶尖的程序员也有可能看不懂自己写的代码,这个和自己的编程风格有关,还是先过了~

[此贴子已经被作者于2017-12-20 13:10编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-12-18 17:46
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 17 楼
 得分:0 
这样优化了一下感觉好多了~

程序代码：
void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;
    size_t t=n-1;
    
    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;

    for (i=a[0];;++i)
    {
        while (i+a[t]>m)
            if (t--<2)
                return ;

        for (j=t;j>k[i];--j)
                k[i+a[j]]=j;
    }
}


[此贴子已经被作者于2017-12-20 13:27编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-12-19 02:52
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 18 楼
 得分:0 
然后又再优化了代码~发现原代码有些地方还可以完善~再次发个完整版代码~

程序代码：
#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#include<string.h>

int Comp(const void* p1,const void* p2);

void Input(size_t** a,size_t** k,size_t* n,size_t* m);

void Fun(size_t a[],size_t k[],size_t n,size_t m);

void Output(size_t a[],size_t k[],size_t m);

int main( void )
{
    size_t* a=NULL;
    size_t* k=NULL;
    size_t n=0;
    size_t m=0;

    Input(&a,&k,&n,&m);

    Fun(a,k,n,m);
    
    Output(a,k,m);

    free(a);
    free(k);

    return 0;
}

int Comp(const void* p1,const void* p2)
{
    if (*(size_t*)p1>*(size_t*)p2)
        return 1;
    else if (*(size_t*)p1<*(size_t*)p2)
        return -1;

    return 0;
}

void Input(size_t** a,size_t** k,size_t* n,size_t* m)
{
    size_t i;

    puts("请输入元素个数和所求定值和:");

    if (scanf("%u%u",(unsigned* )n,(unsigned* )m)!=2)
        exit(0);

    ++*m;
    *a=malloc(*n*sizeof(**a));

    if (*a==NULL)
    exit(0);

    memset(*a,0,*n*sizeof(**a));

    *k=malloc(*m*sizeof(**k));

    if (*k==NULL)
    exit(0);

    memset(*k,-1,*m*sizeof(**k));

    printf("请输入%u个元素:\n",*(unsigned* )n);

    for (i=0;i!=*n;++i)
    if (scanf("%u",(unsigned* )&((*a)[i]))!=1)
        exit(0);
}

void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;

    size_t next=0;
    size_t rear=n-1;
    size_t MinWeight=0;
    
    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;

    for (i=a[0];;++i)
    {

        while (i+a[rear]>m)
        {
            for (;next!=rear&&i>MinWeight+a[next];MinWeight+=a[next++]);

            if (rear--<=next)
                return ;
        }

        for (j=rear;j>k[i];--j)
            k[i+a[j]]=j;
    }
}

void Output(size_t a[],size_t k[],size_t m)
{
    size_t i=0;
    size_t j=0;

    for (;i!=m;++i)
        if (k[i]!=-1)
        {
            printf("%u=%u",(unsigned)i,(unsigned)a[k[i]]);

            for (j=i;j-=a[k[j]];)
                printf("+%u",(unsigned)a[k[j]]);

            puts("");
        }
}


PS:测试代码~

程序代码：
void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;

    size_t next=0;
    size_t rear=n-1;
    size_t MinWeight=0;
    
    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;
        
    for (;next!=rear&&MinWeight+a[next]<=m;MinWeight+=a[next++]);

    if (!next)
        return ;
        
    for (i=a[0];;++i)
    {

        while (i+a[rear]>m)
            if (rear--<next)
                return ;

        for (j=rear;j>k[i];--j)
            k[i+a[j]]=j;
    }
}


[此贴子已经被作者于2017-12-20 17:03编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-12-20 13:22



参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-482627-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。
Powered by Discuz, Processed in 0.496770 second(s), 7 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved