求大神指点，这道题怎么做啊 - C语言论坛

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

求大神指点，这道题怎么做啊

九数组分数

1,2,3...9 这九个数字组成一个分数，其值恰好为1/3，如何组法？

下面的程序实现了该功能，请填写划线部分缺失的代码。

#include <stdio.h>

void test(int x[])
{
    int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
    int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];

    if(a*3==b) printf("%d / %d\n", a, b);
}

void f(int x[], int k)
{
    int i,t;
    if(k>=9){
        test(x);
        return;
    }

    for(i=k; i<9; i++){
        {t=x[k]; x[k]=x[i]; x[i]=t;}
        f(x,k+1);
        _____________________________________________ // 填空处
    }
}

int main()
{
    int x[] = {1,2,3,4,5,6,7,8,9};
    f(x,0);
    return 0;
}

注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。

搜索更多相关主题的帖子: 如何　 return　include　

第 2 楼

得分:7

这是一个典型的全排列组合算法，递归后将交换的数据还原即可，复制递归前的那行代码即可，如果非要不一样，可把k、i对调，结果一样。

收到的鲜花

rjsp 于 2016-02-26 08:44 送鲜花 10朵附言：我很赞同

第 3 楼

得分:7

若是用排列组合的方法，如题目中的方法，确实是难理解。我想出来一个好理解但是比较死的办法。设N为分子，M为分母，且M=N*3，由于有9个数字，所以N只能是四位数，M是五位数。试想N的三倍是五位数，且N的四个数字不能重复，所以N最小是3412，同理N最大是9876。在这个范围内穷举每一个数，只要M*10000+N，即9个数字组成的数没有相同的数字而且没有数字0即可。下面是我的算法。

程序代码：

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

int main()
{
    bool isSameNumberExistsInTwoNumbers(int m,int n);

    //N/M
    int N,M;
    for(N=3412;N<=9876;N++)
    {
        M=N*3;

        if(isSameNumberExistsInTwoNumbers(M,N))
        {
            printf("%d/%d=1/3\n",N,M);
        }
    }

    return 0;
}

bool isSameNumberExistsInTwoNumbers(int m,int n)
{
    int i,j,total=m*10000+n;
    char numChar[10];  //注意长度10是因为末尾要加一个字符串结束标志'\0'
    itoa(total,numChar,10);  //将这个9位数转换成字符串

    for(i=0;i<8;i++)
    {
        for(j=i+1;j<9;j++)
        {
            //比较是否有相同的数字或者有0
            if(numChar[i]==numChar[j]||numChar[i]=='0')  return false;
        }
    }
    if(numChar[8]=='0')  return false;  //检查第9个，上面没有检查到

    return true;
}

下面是程序的运行结果，大家看下对不对。

图片附件: 游客没有浏览图片的权限，请登录或注册

唯实惟新至诚致志

第 4 楼

得分:0

可行，不过楼主题意是帮他填空。另判断是否重复还有更高效的算法，不需要转换为字符串，如下：

bool isSameNumberExistsInTwoNumbers(int m,int n)
{
    int i,total=m*10000+n;
    char numChar[10]={0};  //注意长度10是因为末尾要加一个字符串结束标志'\0'
    for(;total;total/=10)
         numChar[total%10]++;
    for(i=9;i;i--)
         if(numChar[i]!=1)return false;
    return true;
}

第 5 楼

得分:7

回复 4楼拉链

bool isSameNumberExistsInTwoNumbers(int m,int n)
{
    unsigned mark = 0;

    for( n=n*100000+m; n!=0; n/=10 )
        mark |= 1u<<(n%10);

    return mark==0x3FE;
}