| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 700 人关注过本帖, 1 人收藏
标题:大大们。我又来了。。又是程序超时这让小白头疼的事
只看楼主 加入收藏
萝莉小纯情
Rank: 1
等 级:新手上路
帖 子:73
专家分:6
注 册:2012-12-8
收藏
得分:0 
回复 9楼 rjsp
汗!!你们的算法我看不太懂,,刚学c还不是很熟。。
2012-12-14 13:16
萝莉小纯情
Rank: 1
等 级:新手上路
帖 子:73
专家分:6
注 册:2012-12-8
收藏
得分:0 
回复 5楼 rjsp
这个2的倍数我考虑到了。时间减少一半还是超时,
2012-12-14 13:18
萝莉小纯情
Rank: 1
等 级:新手上路
帖 子:73
专家分:6
注 册:2012-12-8
收藏
得分:0 
我现在有事.晚上回去在看看你们的帖子哈
2012-12-14 13:20
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:0 
以下是引用萝莉小纯情在2012-12-14 13:16:32的发言:

汗!!你们的算法我看不太懂,,刚学c还不是很熟。。

看不懂无所谓,反正那代码搞不出来。
我现在会了,我就用 k = 4 手工解给你看一下
假设第一位为1
则最后一位为4,即
     1ab……cd4
*4 = ab……cd41
即d=6
依次类推得到 102564

再假设第一位为2 ……

在这9个数中选一个最小的
2012-12-14 13:33
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:10 
关于魔法数的那个,代码我用 gcc4.7.2 -std=c99 编译通过
程序代码:
#include <stdio.h>
#include <malloc.h>

#include <string.h>

// 以下是个变长字符串
struct varstring
{
    char* p;
    size_t len;
    size_t capacity;
};
void varstring_constructor( struct varstring* vs )
{
    vs->p = (char*)malloc( 10 );
    vs->len = 0;
    vs->capacity = 10;
}
void varstring_destructor( struct varstring* vs )
{
    free( vs->p );
}
void varstring_append( struct varstring* vs, char c )
{
    if( vs->len == vs->capacity )
    {
        char* p = (char*)malloc( vs->capacity*2 );
        memcpy( p, vs->p, vs->capacity );
        free( vs->p );
        vs->p = p;
        vs->capacity *= 2;
    }
    vs->p[vs->len++] = c;
}
void varstring_reverseprint( struct varstring vs )
{
    for( size_t index=vs.len; index!=0; --index )
        putchar( vs.p[index-1] );
}

// 如果第一位数字是f,则这个数值是多少
struct varstring foo( unsigned k, unsigned f )
{
    struct varstring vs;
    varstring_constructor( &vs );

    unsigned c = 0; // 进位
    unsigned a = f;
    while( vs.len==0 || c!=0 || a!=f )
    {
        unsigned t = a*k+c;
        a = t%10;
        c = t/10;
        varstring_append( &vs, a+'0' );
    }

    return vs;
}

// 计算第一位是1,是2,是3……,是9 的九种可能,选择其中最小的那个
struct varstring bar( unsigned k )
{
    struct varstring vss[9];
    for( unsigned i=1; i<10; ++i )
        vss[i-1] = foo( k, i );

    size_t minidx = 0;
    for( unsigned i=1; i<9; ++i )
    {
        if( vss[i].len < vss[minidx].len )
        {
            varstring_destructor( &vss[minidx] );
            minidx = i;
        }
        else
        {
            varstring_destructor( &vss[i] );
        }
    }

    return vss[minidx];
}

// 这个函数,就是最终你需要的
void baz( unsigned k )
{
    printf( "%u = ", k );
    struct varstring vs = bar(k);
    varstring_reverseprint( vs );
    varstring_destructor( &vs );
    putchar( '\n' );
}

int main()
{
    baz(4);
    baz(10);
    baz(11);
    //baz(9999); 输出太长就不贴了

    return 0;
}

输出是
4 = 102564
10 = 10
11 = 100917431192660550458715596330275229357798165137614678899082568807339449541284403669724770642201834862385321
2012-12-14 16:11
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:0 
补充一下
代码中类似 = (char*)malloc 的语句应该将强制转换(char*)去掉(我用C++也试了一把,所以才加上去)。
虽然不少人说加个(char*)更好,这样可以C和C++都能编译通过。但我不这么认为,我认为这在C语言中属于冗余的错误行为。

其次,
    vs->p = (char*)malloc( 10 );
    vs->len = 0;
    vs->capacity = 10;
中的10应该改大点(我一开始设这么小,是想测试一下工作是否正常),即改为
    vs->capacity = 256;
    vs->p = (char*)malloc( vs->capacity );
    vs->len = 0;
2012-12-14 16:18
萝莉小纯情
Rank: 1
等 级:新手上路
帖 子:73
专家分:6
注 册:2012-12-8
收藏
得分:0 
回复 16楼 rjsp
汗。。我多看一会会。。。没怎么明白。。。
2012-12-14 20:12
萝莉小纯情
Rank: 1
等 级:新手上路
帖 子:73
专家分:6
注 册:2012-12-8
收藏
得分:0 
这才发现自己写的那两个程序好水
2012-12-14 20:22
快速回复:大大们。我又来了。。又是程序超时这让小白头疼的事
数据加载中...
 
   



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

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