凑平方数

2016年第7届C/C++大学B组决赛第2题

把0~9这10个数字,分成多个组,每个组恰好是一个平方数,这是能够办到的。
比如:0, 36, 5948721

再比如:
1098524736
1, 25, 6390784
0, 4, 289, 15376
等等…

注意,0可以作为独立的数字,但不能作为多位数字的开始。分组时,必须用完所有的数字,不能重复,不能遗漏。

如果不计较小组内数据的先后顺序,请问有多少种不同的分组方案?

思路分析

要找到 0、4、289、15376,其实就是找其平方根数 0、2、17、124。所以本题可以转换为:找出若干个数,例如4个数a、b、c、d,满足依次递增,且其平方数的组合互不相同。

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

int A[10];
char s[100];
int count = 0;

int is_ok(char s[])
{
    int i, v[10] = {0}, sum=0, n;
    n = strlen(s);
    for (i=0; i<n; i++)
        v[s[i]-'0']=1;
    for (i=0; i<10; i++) sum += v[i];
    return (sum==n)?1:0;
}

void f(int i, int start, int len)
{
    int k, length;
    long long j;
    if (len==10)
    {
        for (k=0; k<i; k++)  printf("%d, ", A[k]);
        printf("\n");
        count++;
        return;
    }
    for (j=start;  ; j++)
    {
		A[i] = j;
        sprintf(s+len, "%lld", j*j);
        length = strlen(s);
        if (length>10) break;
        if (is_ok(s)) f(i+1, j+1, length);
    }
}

int main(int argc, char *argv[])
{
    f(0, 0, 0);
    printf("total = %d\n", count);
    return 0;
}
2017年5月23日 | 归档于 蓝桥杯
标签:
本文的评论功能被关闭了.