| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1913 人关注过本帖, 1 人收藏
标题:一道简单算法题目,看看各位最简单的解法
只看楼主 加入收藏
取消关键字高亮
lowrie
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:81
专家分:138
注 册:2015-3-12
收藏
得分:0 
回复 18楼 jklqwe111
层主能不能讲一下你的逻辑,没看懂
2015-04-02 09:41
jklqwe111
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:35
帖 子:336
专家分:1135
注 册:2014-4-13
收藏
得分:0 
回复 21楼 lowrie
思路是这样的,先确定第一组的范围,再进行循环,先构造一个符合比例关系的数字w,再判断各个位上是否有重复,方法是:遍历这一数字w,用一组标志记录那九个数字是否出现,每次记录时,判别以前是否出现,若出现则判定w不符合要求,进行下一个循环,如果9个数字全部出现一次,输出结果。这与9楼的方法是一样的,只是那里用数组做标志记录,我是以一个数做记录,用这个数的1位标记1是否出现,2位标记2是否出现,九个数用到了9位,标记位的读写就用与  ,或来实现。
2015-04-02 11:25
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
按照人的思维方式的方法,我想效率会比较高些。
程序代码:
#include <stdio.h>

struct carray { int d[3]; };

/* *1,*2,*3的个位数 */
char tab_digit[] = {    
        0, 0, 0, 1, 2, 3,
        2, 4, 6, 3, 6, 9,
        4, 8, 2, 5, 0, 5,
        6, 2, 8, 7, 4, 1,
        8, 6, 4, 9, 8, 7};
/* *1,*2,*3的进位 */
char tab_carray[] = { 
        0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0,
        0, 0, 1, 0, 1, 1,
        0, 1, 1, 0, 1, 2,
        0, 1, 2, 0, 1, 2};

int have_digit(unsigned flags, int i)
{
    return (flags >> i) & 1;
}

int set_digit(unsigned *flags, struct carray *_carray, int i)
{
    unsigned flags2 = 0;
    int *carray = _carray->d;
    int a = carray[0] + tab_digit[3*i+0];
    int b = carray[1] + tab_digit[3*i+1];
    int c = carray[2] + tab_digit[3*i+2];

    carray[0] = tab_carray[3*i+0] + !!(a >= 10);
    carray[1] = tab_carray[3*i+1] + !!(b >= 10);
    carray[2] = tab_carray[3*i+2] + !!(c >= 10);

    flags2 = (1 << (a >= 10 ? a - 10 : a)) |
             (1 << (b >= 10 ? b - 10 : b)) |
             (1 << (c >= 10 ? c - 10 : c));

    if (!flags2 || (flags2 & *flags))
        return 0;
    return (*flags |= flags2);
}


int next_digit(unsigned flags, int i)
{
    flags |= (1 << ++i) - 1;
    /* 可以直接用1条汇编指令优化 */
    for (; i <= 9; ++i)
        if (!have_digit(flags, i))
            return i;
    return 0;
}

void foo(void)
{
    int i, j, k;

    for (i = 1; i <= 9; ++i) { /* 9次循环 */
        unsigned flags0 = 0;
        struct carray carray0 = {{0}};
        set_digit(&flags0, &carray0, i);

        for (j = 0; (j = next_digit(flags0, j)); ) { /* 6次循环 */
            struct carray carray1 = carray0;
            unsigned flags1 = flags0;

            if (!set_digit(&flags1, &carray1, j))
                continue;

            k = next_digit(flags1, 0);
            if (set_digit(&flags1, &carray1, k) && flags1 == 0x3FE) {
                if (!(carray1.d[0] | carray1.d[1] | carray1.d[2])) {
                    int n = i + j * 10 + k * 100;
                    printf("%d %d %d\n", n, 2*n, 3*n);
                }
            }            
        }
    }
}

int main(void) 
{
    foo();
    return 0;
}


[ 本帖最后由 wfoo 于 2015-4-2 15:24 编辑 ]
2015-04-02 15:14
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
回复 23楼 wfoo
oh!你这肯定不是在编程,你这是在秀你的基本功。你这巨型代码使用了c所有知识,甚至提到汇编(反正我看的是云里雾里),顿时让9楼用9行语句完成的相同功能的代码靠边站、相形见拙啊。
只选贵的,不选对的!
2015-04-02 15:44
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
回复 24楼 xzlxzlxzl
这个就是我们自己如果在解这个题的思考方式,用flags的第1位到第9位表示相应的数字是不是已经使用。
首先从个位i考虑起, 比如i=9(0:括号内的为进位),那么另外2个数的个位为8(1), 7(2) [个位: 9 8 7]
   这样十位数只能为1,2,3,4,5,6; 假设循环取到底十位数为1(0),
         那么不靠路进位另2个数为2(0),3(0); 加上前面的进位则这两个数为3(0),5(0) [十位: 1 3 5]
            那么百位只能是2,4,6;因为第一个数最小,所以这3个数 [百位: 2 4 6]
   只要在判断过程中比较flags的标志位是否重复就可以确保每个数字的唯一性。 [219 438 657]是符合要求的。
2015-04-02 16:02
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
回复 25楼 wfoo
这只是你的思考方式吧。我虽不会写c代码,但自觉思考编程算法不会太差,这题我如果用vb写会更精炼些。
2015-04-02 16:14
wfoo
Rank: 3Rank: 3
等 级:论坛游侠
威 望:7
帖 子:120
专家分:134
注 册:2011-8-6
收藏
得分:0 
我说的思维方式不是编程思考方式,假设这是一个数学题,你不可能用i=123; 。。。333一个一个的试吧?这样是不是也会像我上面的那样去想?这样去算的计算量起码小5倍,即使不编程,口算应该也可以很快得出结果。
再者,如果不考虑效率,用脚本应该可以几行代码就行了。

[ 本帖最后由 wfoo 于 2015-4-2 16:27 编辑 ]
2015-04-02 16:23
快速回复:一道简单算法题目,看看各位最简单的解法
数据加载中...
 
   



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

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