标题:某人有m张8角和n张5角的邮票,使用这些邮票能组合出多少种不同面值的邮资,m ...
只看楼主
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:432
帖 子:10064
专家分:41463
注 册:2014-5-20
得分:0 
以下是引用xzlxzlxzl在2017-3-24 21:15:00的发言:

吹版主总结下嘛,肯定有个不需要循环的简明规律。

严格的公式推导和验证比较费时伤神。
2017-03-24 21:28
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:432
帖 子:10064
专家分:41463
注 册:2014-5-20
得分:0 
回复 18楼 吹水佬
显示组合情况,应该没重复了吧:

#include <stdio.h>
#include <stdlib.h>
main()     
{     
    int i, j, k, z, m, n, count=0;
    printf("分别输入8角和5角的张数:");
    scanf("%d%d",&m,&n);
    k = 8*m+5*n+1;
    char *c = (char*)calloc(k, sizeof(char));
    int *ci = (int*)calloc(k, sizeof(int));
    int *cj = (int*)calloc(k, sizeof(int));
    for (i=0; i<=m; i++)  
    {
        for(j=0; j<=n; j++)  
        {
            z = i*8+j*5;
            c[z] = 1;
            ci[z] = i;
            cj[z] = j;
            //c[z]++;
        }
    }
    for (i=1; i<k; i++) //c[0]的不算
    {
        if (c[i])
        {
            count++;
            printf("组合%d\t%d张8角+%d张5角\t%d角\n", count, ci[i], cj[i], i);
        }
    }
    printf("共有%d种组合\n",count);
    free(c);
    free(ci);
    free(cj);
}
2017-03-24 21:30
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
得分:0 
程序代码:
m1 * 8 + n1 * 5 = m2 * 8 + n2 *5


(m1 - m2)/(n2 - n1)  =                       5/8 

m1 - m2  (m1 != m2, 且都不大于m)取值可能个数 Vm1       
n2 - n1  (n1 != n2, 且都不大于n)取值可能个数 Vn1       

重复数 Vm1 * Vn1 


没写代码证明, 这样  后面翻倍的结果相交了


[此贴子已经被作者于2017-3-24 22:15编辑过]

2017-03-24 21:34
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
回复 19楼 吹水佬
把0面值也算进去了~结果减1就行了~
收到的鲜花

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-03-24 22:04
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
得分:0 
其实规律理解了就很简单~那条公式里面本来就体现了规律~当m<5或者n<7时是不能凑合出重复数的~证明如下~

不难证明重复的最小生成条件是用5张面值为8的来换取8张面值为5的~然而当i>=5时并且j<=m-8时总能找到与其面值相等的另一种取法~而另一种取法可能也包含了第三种重复取法……这样递推下去的极限就是一种有规律的取法~就是满足i<5或者j>n-8  这种状态就意味着不能再获得新的重复取法了~所以这就证明了所有重复状态都包含了i>=5并且j<=n-8中的所有状态~到这里~这就不难推导出那条公式了~
收到的鲜花
  • lzd7440882017-03-31 23:38 送鲜花  3朵   附言:我很赞同

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



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




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

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