出个简单编程题，有兴趣的可以做一下。 - C语言论坛

已结贴√ 问题点数：20 回复次数：8

出个简单编程题，有兴趣的可以做一下。

有一个包含26个金额的数组，分别为13619.55,75790.12,281455.16,261404.62,335152.80,369695.85,128886.35,264025.39,481521.2,81765.72,114028.92,278608.89,95806.38,208700.44,461393.19,285090.22,340276.66,112633.4,410825.55,82127.74,405637.15,263896.29,291135.28,461479.99,258011.72,371517.40。
已知这些金额中的一个或一些的和为3220324.82。
请编程求出满足这个和的金额序列，输出为数组下标列表即可。
要求可在https://www.bccn.net/run/上运行，并且运行时间不大于500ms。

举例，如果只有4个金额 1 2 3 4，和为5。
那么输出为2组下标，分别为 0 3 和 1 2。

搜索更多相关主题的帖子: 编程　金额　兴趣　下标　输出　

第 2 楼

得分:0

0.6秒，超了，先记下来

程序代码：

#include <stdio.h>
#include <time.h>

int main( void )
{
    clock_t t0 = clock();

    const double s_[] = { 13619.55,75790.12,281455.16,261404.62,335152.80,369695.85,128886.35,264025.39,481521.2,81765.72,114028.92,278608.89,95806.38,208700.44,461393.19,285090.22,340276.66,112633.4,410825.55,82127.74,405637.15,263896.29,291135.28,461479.99,258011.72,371517.40 };
    const double result_ = 3220324.82;

    enum { S_SIZE = sizeof(s_)/sizeof(*s_) };
    unsigned result = (unsigned)(result_*100 + 0.5);
    unsigned s[S_SIZE];
    for( size_t i=0; i!=S_SIZE; ++i )
        s[i] = (unsigned)(s_[i]*100 + 0.5);

    unsigned sum = 0;
    for( unsigned i=1; i<(1u<<S_SIZE); ++i )
    {
        unsigned p = (i-1)^i;
        unsigned q = p&i;
        for( unsigned j=0; p; p>>=1,q>>=1,++j )
        {
            if( (p&1) && (q&1) )
                sum += s[j];
            else if( (p&1) )
                sum -= s[j];
        }

        if( sum == result )
        {
            for( unsigned j=0,t=i; t!=0; t>>=1,++j )
            {
                if( (t&1) )
                    printf( " %u", j );
            }
            putchar( '\n' );
        }
    }

    clock_t t1 = clock();
    printf( "耗时 %.g 秒\n", (t1-t0+0.0)/CLOCKS_PER_SEC );
}

第 3 楼

得分:0

回复 2楼 rjsp

提示一下，不止一组答案。

第 4 楼

得分:0

看似组合问题

第 5 楼

得分:0

floor 2, wonderful code! very impressive by using dynamic p & q

I added some readable note

程序代码：

#include <stdio.h>
#include <time.h>

int main(int argc, char *argv[])
{
    clock_t t0 = clock();

    const double s_[] = {1, 3, 5, 2, 4, 6, 10};
    const double result_ = 10;
    //s_size = 7
    enum {S_SIZE = sizeof(s_) / sizeof(*s_)};
    unsigned result = (unsigned)(result_*100 + 0.5);
    unsigned s[S_SIZE];
    //extend to integer
    for (size_t i = 0; i != S_SIZE; ++i)
        s[i] = (unsigned)(s_[i]*100 + 0.5);
    unsigned sum = 0;
    //i < 2^7
    for (unsigned i = 1; i < (1u << S_SIZE); ++i) {
        //p_flag set vector
        unsigned p = (i - 1) ^ i;
        //q_flag clr vector
        unsigned q = p & i;
//#define PRINT_ON
#ifdef PRINT_ON
        printf("i = %d\n", i);
        printf("p = %u\n", p);
        printf("q = %u\n", q);
#endif
        for(unsigned j = 0; p; p >>= 1, q >>= 1, ++j) {
            if((p & 1) && (q & 1)) {
                //set vector
                sum += s[j];
#ifdef PRINT_ON
                printf("if s[%d] = %u\n", j, s[j]);
                printf("if sum = %u\n", sum);
#endif
            } else if((p & 1)) {
                //clr vector
                sum -= s[j];
#ifdef PRINT_ON
                printf("else s[%d] = %u\n", j, s[j]);
                printf("else sum = %u\n", sum);
#endif
            }
        }

        if( sum == result ) {
            for (unsigned j = 0, t = i; t != 0; t >>= 1, ++j) {
#ifdef PRINT_ON
                printf("t = %u\n", t);
#endif
                if( (t&1) )
                    printf( " %u", j );
            }
            putchar( '\n' );
        }
    }

    clock_t t1 = clock();
    printf( "耗时 %.g 秒\n", (t1-t0+0.0)/CLOCKS_PER_SEC );
}

output sample:

const double s_[] = { 1, 3, 5, 2, 4, 6, 10};
if s[0] = 100
if sum = 100//0
if s[1] = 300
if sum = 300//1
if s[0] = 100
if sum = 400//0,1
if s[2] = 500
if sum = 500//2
if s[0] = 100
if sum = 600//0,2
if s[1] = 300
if sum = 800//1,2
if s[0] = 100
if sum = 900//0,1,2
if s[3] = 200
if sum = 200//3
if s[0] = 100
if sum = 300//0, 3
if s[1] = 300
if sum = 500//1, 3
if s[0] = 100
if sum = 600//0, 1, 3
if s[2] = 500
if sum = 700//2, 3
if s[0] = 100
if sum = 800//0, 2, 3
if s[1] = 300
if sum = 1000//1, 2, 3

p = 1
q = 1
if s[0] = 100 //set
if sum = 100
p = 3
q = 2
else s[0] = 100 //clr
else sum = 0
if s[1] = 300
if sum = 300 //set next one in the meantime

[此贴子已经被作者于2021-10-18 18:35编辑过]

第 6 楼

得分:0

wonderful thinking

basement algorithm:
pseudo code description:
/* all these operation controlled via index p & q */
vector.load(current);
compare equal if not
vector.clr(previous) && vector.load(next)

第 7 楼

得分:0

my way~
//online parser: https://www.bccn.net/run/

程序代码：

#include <stdio.h>

#define CHECK_SUM 10

void check_sum(char *log, int *d, int len)
{
    int i;
    
    puts(log);
    for (i = 0; i < len; i++) {
        if (CHECK_SUM == d[i]) printf("set %d hit!\n", i);
        //else puts("pass");
    }
}

int main(int argc, char *argv[])
{
    int sum, i, j;

#define C71 7
    int d1[C71] = {1, 3, 5, 2, 4, 6, 10};
/***************** pre-generated by another program named: array_seperated.c ******************/
#define C72 (7 * 6) >> 1 
    int d2[C72] = {
#define src d1
        /*  0 */src[0] + src[1], src[0] + src[2], src[0] + src[3],
        /*  3 */src[0] + src[4], src[0] + src[5], src[0] + src[6],
        /*  6 */src[1] + src[2], src[1] + src[3], src[1] + src[4],
        /*  9 */src[1] + src[5], src[1] + src[6], src[2] + src[3],
        /* 12 */src[2] + src[4], src[2] + src[5], src[2] + src[6],
        /* 15 */src[3] + src[4], src[3] + src[5], src[3] + src[6],
        /* 18 */src[4] + src[5], src[4] + src[6], src[5] + src[6]
    };
#define C73 (7 * 6 * 5) / (3 * 2)
    int d3[C73] = {
        /*  0 */d2[0] + src[2],  d2[0] + src[3],  d2[0] + src[4],
        /*  3 */d2[0] + src[5],  d2[0] + src[6],  d2[1] + src[3],
        /*  6 */d2[1] + src[4],  d2[1] + src[5],  d2[1] + src[6],
        /*  9 */d2[2] + src[4],  d2[2] + src[5],  d2[2] + src[6],
        /* 12 */d2[3] + src[5],  d2[3] + src[6],  d2[4] + src[6],
        /* 15 */d2[6] + src[3],  d2[6] + src[4],  d2[6] + src[5],
        /* 18 */d2[6] + src[6],  d2[7] + src[4],  d2[7] + src[5],
        /* 21 */d2[7] + src[6],  d2[8] + src[5],  d2[8] + src[6],
        /* 24 */d2[9] + src[6],  d2[11] + src[4], d2[11] + src[5],
        /* 27 */d2[11] + src[6], d2[12] + src[5], d2[12] + src[6],
        /* 30 */d2[13] + src[6], d2[15] + src[5], d2[15] + src[6],
        /* 33 */d2[16] + src[6], d2[18] + src[6]
    };
#define C74 (7 * 6 * 5 * 4) / (4 * 3 * 2)
    int d4[C74] = {
        /*  0 */d3[0] + src[3],  d3[0] + src[4],  d3[0] + src[5],
        /*  3 */d3[0] + src[6],  d3[1] + src[4],  d3[1] + src[5],
        /*  6 */d3[1] + src[6],  d3[2] + src[5],  d3[2] + src[6],
        /*  9 */d3[3] + src[6],  d3[5] + src[4],  d3[5] + src[5],
        /* 12 */d3[5] + src[6],  d3[6] + src[5],  d3[6] + src[6],
        /* 15 */d3[7] + src[6],  d3[9] + src[5],  d3[9] + src[6],
        /* 18 */d3[10] + src[6], d3[12] + src[6], d3[15] + src[4],
        /* 21 */d3[15] + src[5], d3[15] + src[6], d3[16] + src[5],
        /* 24 */d3[16] + src[6], d3[17] + src[6], d3[19] + src[5],
        /* 27 */d3[19] + src[6], d3[20] + src[6], d3[22] + src[6],
        /* 30 */d3[25] + src[5], d3[25] + src[6], d3[26] + src[6],
        /* 33 */d3[28] + src[6], d3[31] + src[6]
    };
/***************** pre-generated by another program named: array_seperated.c ******************/
    check_sum("check d1...", d1, C71);
    check_sum("check d2...", d2, C72);
    check_sum("check d3...", d3, C73);
    check_sum("check d4...", d4, C74);
    
    return 0;
}

output sample:
check d1...
set 6 hit!
check d2...
set 18 hit!
check d3...
set 3 hit!
set 6 hit!
set 15 hit!
check d4...
set 4 hit!
-----------auto generate sequence array-----------

程序代码：

#include <stdio.h>
#include <string.h>

typedef struct array_desc{
    char _head[256];
    char _body[1024];
    char _tail[8];
}svad, *spad;

int main(int argc, char *argv[])
{
#define C71 7
    int d1[C71] = {1, 3, 5, 2, 4, 6, 10};
    char *_d2[3] = {
        /* C72 */"010203040506121314151623242526343536454656",
        /* C73 */"02030405061314151624252635364663646566747576858696116125126136155156166186",
    };
    char *_head[3] = {
        "#define C72 (7 * 6) >> 1\nint d2[C72] = {",
        "#define C73 (7 * 6 * 5) / (3 * 2)\nint d3[C73] = {"
    };
    char *_body = "/*  i */d1[x] + d1[x], d1[x] + d1[x], d1[x] + d1[x],\n";
    char *_tail = "};";

    int i, j, idx;
    static svad vad;
    strcpy((&vad)->_head, _head[0]);
    /* C72 */
    for (i  = 0; i < 7; i++)
        strcpy((&vad)->_body + strlen((&vad)->_body), _body);
    strcpy((&vad)->_tail, _tail);
#if 1
    for (i = j = idx = 0; i < strlen((&vad)->_body); i++) {
#define tag_I 'i'
#define tag_X 'x'
#define tag_Y 'y'
#define tag_Z 'z'
#define dig_lize(_n, op) ((_n) op 10) + 0x30
        if (tag_I  == (&vad)->_body[i]) {
            (&vad)->_body[i - 1] = dig_lize(3 * idx, /);
            (&vad)->_body[i] = dig_lize(3 * idx++, %);
        } else if (tag_X  == (&vad)->_body[i]) {
            (&vad)->_body[i] = _d2[0][j++];
        } else if (tag_Y  == (&vad)->_body[i]) {
            (&vad)->_body[i] = _d2[0][j++];
            (&vad)->_body[++i] = _d2[0][j++];
        }
    }
#endif
    puts((&vad)->_head);
    printf("%s", (&vad)->_body);
    puts((&vad)->_tail);

    return 0;
}

output sample:

#define C72 (7 * 6) >> 1
int d2[C72] = {
/* 00 */d1[0] + d1[1], d1[0] + d1[2], d1[0] + d1[3],
/* 03 */d1[0] + d1[4], d1[0] + d1[5], d1[0] + d1[6],
/* 06 */d1[1] + d1[2], d1[1] + d1[3], d1[1] + d1[4],
/* 09 */d1[1] + d1[5], d1[1] + d1[6], d1[2] + d1[3],
/* 12 */d1[2] + d1[4], d1[2] + d1[5], d1[2] + d1[6],
/* 15 */d1[3] + d1[4], d1[3] + d1[5], d1[3] + d1[6],
/* 18 */d1[4] + d1[5], d1[4] + d1[6], d1[5] + d1[6],
};

[此贴子已经被作者于2021-10-20 21:47编辑过]

第 8 楼

得分:20

这个需要 0.3秒，勉强符合要求

程序代码：

#include <stdio.h>
#include <stdbool.h>
#include <time.h>

int main( void )
{
    clock_t t0 = clock();

    // 输入数据
    const double s_[] = { 13619.55,75790.12,281455.16,261404.62,335152.80,369695.85,128886.35,264025.39,481521.2,81765.72,114028.92,278608.89,95806.38,208700.44,461393.19,285090.22,340276.66,112633.4,410825.55,82127.74,405637.15,263896.29,291135.28,461479.99,258011.72,371517.40 };
    const double result_ = 3220324.82;

    // 转换成整型，以避免累加时丢失精度
    enum { S_SIZE = sizeof(s_)/sizeof(*s_) };
    unsigned result = (unsigned)(result_*100 + 0.5);
    unsigned s[S_SIZE];
    for( size_t i=0; i!=S_SIZE; ++i )
        s[i] = (unsigned)(s_[i]*100 + 0.5);

    //
    bool mask[1+S_SIZE] = { true };
    unsigned sums[1+S_SIZE] = { 0 };
    while( 1 )
    {
        // 从右至左，找到第一个被选者
        size_t index;
        for( index=1+S_SIZE; index!=0 && !mask[index-1]; --index );
        if( index == 0 ) // 找不到，那就结束了
            break;

        // 将找到的这个被选者 改为 不被选
        mask[index-1] = false;
        sums[index-1] = index==1 ? 0 : sums[index-2];

        // 然后从此数开始往右，能选则选
        for( ; index!=1+S_SIZE; ++index )
        {
            if( result-sums[index-1] >= s[index-1] )
            {
                mask[index] = true;
                sums[index] = sums[index-1] + s[index-1];
            }
            else
            {
                mask[index] = false;
                sums[index] = sums[index-1];
            }
        }

        //
        if( sums[S_SIZE] == result )
        {
            for( size_t i=0; i!=S_SIZE; ++i )
            {
                if( mask[1+i] )
                    printf( " %zu", i );
            }
            putchar( '\n' );
        }
    }

    clock_t t1 = clock();
    printf( "耗时 %.g 秒\n", (t1-t0+0.0)/CLOCKS_PER_SEC );
}

[此贴子已经被作者于2021-10-19 10:10编辑过]

第 9 楼

得分:0

以下是引用diycai在2021-10-18 17:03:59的发言：

提示一下，不止一组答案。

除“0 3 4 5 7 9 12 18 21 22 23 25”之外，还有吗？你说一个，我来检查一下

第 10 楼

得分:0

//online parser: https://www.bccn.net/run/?lang=c

程序代码：

#include <stdio.h>
#include <stdbool.h>
#include <time.h>

int main( void )
{
    clock_t t0 = clock();

    // 输入数据
    const double s_[] ={1, 3, 5, 2, 4, 6, 10};
    const double result_ = 10;

    // 转换成整型，以避免累加时丢失精度
    enum { S_SIZE = sizeof(s_)/sizeof(*s_) };
    unsigned result = (unsigned)(result_*100 + 0.5);
    unsigned s[S_SIZE];
    for( size_t i=0; i!=S_SIZE; ++i )
        s[i] = (unsigned)(s_[i]*100 + 0.5);

    //
    bool mask[1+S_SIZE] = {true};
    unsigned sums[1+S_SIZE] = {0};
    while(1) {
        //从右至左，找到第一个被选者
        size_t index;
        for(index = 1 + S_SIZE; index != 0 && !mask[index-1]; --index);
        if( index == 0 ) break;

        //将找到的这个被选者 改为 不被选
        mask[index-1] = false;
        sums[index-1] = index == 1 ? 0 : sums[index-2];
        
        //然后从此数开始往右，能选则选
        for( ; index!=1+S_SIZE; ++index )
        {
            if (result-sums[index-1] >= s[index-1]) {
                mask[index] = true;
                sums[index] = sums[index-1] + s[index-1];
#define PRINT_ON
#ifdef PRINT_ON
                printf("if sum[%zu] = %u\n", index, sums[index]);
#endif
            } else {
                mask[index] = false;
                sums[index] = sums[index-1];
#ifdef PRINT_ON
                printf("else sum[%zu] = %u\n", index, sums[index]);
#endif
            }
        }

        //
        if( sums[S_SIZE] == result )
        {
            for( size_t i=0; i!=S_SIZE; ++i )
            {
                if( mask[1+i] )
                    printf( " %zu", i );
            }
            putchar( '\n' );
        }
    }

    clock_t t1 = clock();
    printf( "耗时 %.g 秒\n", (t1-t0+0.0)/CLOCKS_PER_SEC );
}

logout:
if sum[1] = 100 access data_1 in
if sum[2] = 400 access data_3 in
if sum[3] = 900 access data_5 in
else sum[4] = 900 probe data_2 pass
else sum[5] = 900 probe data_4 pass
else sum[6] = 900 probe data_6 pass
else sum[7] = 900 probe data_10 pass
if sum[4] = 600 backtrace from data_3 in
if sum[5] = 1000 access data_4 in
else sum[6] = 1000 probe data_6 pass
else sum[7] = 1000 probe data_10 pass
0 1 3 4 round over hit

[此贴子已经被作者于2021-10-19 10:48编辑过]