资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

求数组部分和(C语言)-创新互联

假设有一个数组a[N] N<=20
能不能从数组a中任选M个元素(M<=N),使得其和为K。

佳县网站建设公司创新互联公司,佳县网站设计制作,有大型网站制作公司丰富经验。已为佳县1000+提供企业网站建设服务。企业网站搭建\外贸营销网站建设要多少钱,请找那个售后服务好的佳县做网站的公司定做!

解题思路:穷举法

利用穷举法,将所有的情况进行运算,直到找到该子数组为止。
我们利用二进制来表示数组中的数据是否在子数组中,其中0表示不在,1表示在。
例如数组a为{21, 1, 35, 15, 32, 12, 5, 7},我们需要找到三个数之和为79。
则用二进制进行表示则为00110100(这里要注意的是,二进制表示与数组的顺序是反过来的,则00000001,表示的是a[0],而不是a[7])。
同时,我们对该二进制数据进行右移运算,并与1进行与运算,当结果为1的时候,我们将数据进行相加,如果与K相等并且二进制表示中的1的个数与M相等,则数组a中有M个元素其和为K。

针对于这个算法,我们需要利用到两个for循环,第一个for循环用来对各种情况进行遍历,第二个for循环用来对第一个循环中的情况进行运算,即:

for (int i = 0; i< (1<< N); i++) // i用于统计各种情况
{for (int j = 0; j< N; j++)
    {……
    }
}

对于第二个循环中,我们应该如何去针对于第一个循环中的情况进行运算呢?

例如,数组a为{21, 1, 35, 15, 32, 12, 5, 7},我们需要找到三个数之和为79,而这中情况用二进制进行表示则为00110100
在第二个循环中,当j=2时,该二进制数进行右移两位,结果为00001101,我们再对它与1进行与运算,结果为1
所以,我们找到了我们需要的第一个数,即为a[2],以此类推,我们就会找到剩下的两个数

所以第二个循环的j表示的是右移的位数,当与1与运算的结果为1时,我们才进行计算,为0时不计算,所以我们还需要一个条件语句进行判断即:

for (int i = 0; i< (1<< N); i++) // i用于统计各种情况
{for (int j = 0; j< N; j++)
    {if ((i >>j) & 1) //通过与1进行与运算,来对所有情况进行求和
    	{	}
    }
    if (sum == K && count == M)//打印结果
    {……
    }
}

最后我们的最终代码应该为

#include#define N 20
int main()
{int sum;      //用来计算M个元素之和
    int count;    //用来统计已经相加的元素个数,用于判断是否和M相等
    int flag = 0; //用来标记结果,1表示数组a中有M个元素其和为K,0表示没有
    int M, K;
    int a[N] = {21, 1, 35, 15, 32, 12, 5, 7};
    scanf("%d %d", &M, &K);
    for (int i = 0; i< (1<< N); i++) // i用于统计各种情况
    {sum = 0;
        count = 0; //每结束一次循环,sum、count都需要重新置零
        for (int j = 0; j< N; j++)
        {if ((i >>j) & 1) //通过与1进行与运算,来对所有情况进行求和
            {sum += a[j];
                count++;
            }
        }
        if (sum == K && count == M)//打印结果
        {flag = 1;
            count = 0;
            printf("数组a中存在%d个元素其和为%d\n", M, K);
            for (int j = 0; j< N; j++)
            {if ((i >>j) & 1) 
                {count++;
                    if (count == M)
                        printf("%d", a[j]);
                    else
                        printf("%d+", a[j]);
                }
            }
            printf("=%d\n", K);
            break;
        }
    }
    if (flag == 0)//如果数组中不存在M个元素其和为K
    {printf("数组a中不存在%d个元素其和为%d\n", M, K);
    }
}

我们对代码进行编译与运行,结果为:
在这里插入图片描述
如有错误,请批评指出,希望各位大佬指点

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站题目:求数组部分和(C语言)-创新互联
当前路径:http://cdkjz.cn/article/dscpoe.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220