当前位置：网站首页>c语言之 练习题1 大贤者福尔：魔法数，神奇的等式

c语言之 练习题1 大贤者福尔：魔法数，神奇的等式

2022-08-10 21:05:00 【水w】

目录

魔法数

给定不大于NN的整数a, b, c, d (1 \le a \le b \le c \le d \le N)a,b,c,d(1≤a≤b≤c≤d≤N)，可能存在关系a^x+b^x+c^x=d^xax+bx+cx=dx。

神奇的等式

代码1:

 代码2：

魔法数

给定不大于NN的整数a, b, c, d (1 \le a \le b \le c \le d \le N)a,b,c,d(1≤a≤b≤c≤d≤N)，可能存在关系a^x+b^x+c^x=d^xax+bx+cx=dx。

大贤者福尔最近迷上了数学，他研究发现有些神奇的数似乎具有某种魔力。于是他开始研究自然数，发现某个范围内的一些数，经过一定规则运算后的和，等于另一个数按同样规则计算后的值。具体来说，给定不大于NN的整数a, b, c, d (1 \le a \le b \le c \le d \le N)a,b,c,d(1≤a≤b≤c≤d≤N)，可能存在关系a^x+b^x+c^x=d^xax+bx+cx=dx。

福尔想知道在给定的范围NN中，有多少数能够满足这种关系？

  • 输入:输入数据有若干行，每行包括两个整数x, N,(2 \le x \le 3, 1 \le N \le 100x,N,(2≤x≤3,1≤N≤100。
  • 输出:对每组测试数据，先输出样例编号Case c:，c为当前测试样例的组号，从1开始。随后按照a, b, ca,b,c的自然序依次输出结果。若不存在满足条件的数，则输出No such numbers.。
  • 示例输入：
3 4
3 6
  • 示例输出：
Case 1: No such numbers.
Case 2: 3^3+4^3+5^3=6^3

代码1： 

#include<stdio.h>
#include<math.h>
long Pow(short a, short x);
int main()
{
    short x, N;
    short a, b, c, d;
    long K = 1;
    bool flag;
    while(scanf("%hd%hd", &x, &N) != EOF)
    {
        flag = false;
        printf("Case %ld:\n", K ++);
        for(a = 1; a <= N; a ++)
        {
            for(b = a; b <= N; b ++)
            {
                for(c = b; c <= N; c ++)
                {
                    for(d = c; d <= N; d ++)
                    {
                        if(Pow(a, x) + Pow(b, x) + Pow(c, x) == Pow(d, x))
                        {
                            printf("%hd^%hd+%hd^%hd+%hd^%hd=%hd^%hd\n", a, x, b, x, c, x, d, x);
                            flag = true;
                        }
                    }
                }
            }
        }
        if(flag == false)
        {
            printf("No such numbers.\n");
        }
    }
    return 0;
}
/* 计算a^x */
long Pow(short a, short x)
{
    short i;
    long s = 1;
    for(i = 1; i <= x; i ++)
    {
        s *= a;
    }
    return s;
}

代码2： 

#include<stdio.h>
#include<math.h>
int main()
{
	int x, N, c = 0;
	while (scanf("%d %d", &x, &N) == 2)
	{
		int arr[105]; int flag = 0;
		for (int i = 1; i <= N; i++)
			arr[i] = pow(i, x);
		printf("Case %d:\n", ++c);
		for (int i = 1; i <= N; i++)
		{
			for (int j = i; j <= N; j++)
			{
				for (int k = j; k <= N; k++)
				{
					int sum = arr[i] + arr[j] + arr[k];
					for (int t = k + 1; t <= N; t++)
					{
						if (sum == arr[t])
						{
							flag = 1;
							printf("%d^%d+%d^%d+%d^%d=%d^%d\n", i, x, j, x, k, x, t, x);
							break;
						}
						if (arr[t] > sum)break;
					}
				}
			}
		}
		if (!flag)
			printf("No such numbers.\n");
	}
	return 0;
}

 神奇的等式

大贤者福尔在研究数学问题时，发现有一些自然数能够构成一个形如下式的等式，颇为神奇。{x_0x_1x_2x_3x_4 \over x_5x_6x_7x_8x_9} = Nx5​x6​x7​x8​x9​x0​x1​x2​x3​x4​​=N其中x_i, (0 \le i \le 9)xi​,(0≤i≤9)为0−90−9之间的数字，且各不相同。福尔想知道给定NN的值时，有多少数能够满足这种关系？

  • 输入：输入数据有若干行，每行包括单个整数N (2 \le N \le 79)N(2≤N≤79)。
  • 输出：对每行输入数据，先在单独的行中输出如Case x:的测试样例信息，x为测试样例编号，从1开始。若存在满足条件的数值，则分别按分母递减的顺序依次在独立的行中输出各个等式；若不存在满足条件的数，则在单独的行中输出No such numbers.。每个输出结果的前面保留4个空格。
  • 示例输入：
68 69
  • 示例输出：
Case 1: 98736/01452=68
Case 2: No such numbers

代码1:

#include<stdio.h>
#define Yes 1
#define No 0
typedef short Status;
Status FindDuplication(short *temp, short N);

/* 
大贤者福尔在研究数学问题时，发现有一些自然数能够构成一个形如下式的等式，颇为神奇。
{x_0x_1x_2x_3x_4 \over x_5x_6x_7x_8x_9} = Nx5​x6​x7​x8​x9​x0​x1​x2​x3​x4​​=N其中x_i, (0 \le i \le 9)xi​,(0≤i≤9)为0−90−9之间的数字，且各不相同。
福尔想知道给定NN的值时，有多少数能够满足这种关系？
*/

int main()
{
    short N;
    long x, y;
    short temp[10];
    bool flag;
    long K = 1;
    while(scanf("%hd", &N) != EOF)
    {
        flag = false;
        printf("Case %ld:\n", K ++);
        /* 以分母为基准 */
        for(y = 99999 / N; y > 0; y --)
        {
            x = y * N;
            /* 此时 x % y == 0 && x / y == N 成立 */
            temp[0] = x / 10000;
            temp[1] = x / 1000 % 10;
            temp[2] = x / 100 % 10;
            temp[3] = x / 10 % 10;
            temp[4] = x % 10;
            if(FindDuplication(temp, 5) == Yes)
            {
                continue;
            }
            temp[5] = y / 10000;
            temp[6] = y / 1000 % 10;
            temp[7] = y / 100 % 10;
            temp[8] = y / 10 % 10;
            temp[9] = y % 10;
            if(FindDuplication(temp + 5, 5) == Yes)
            {
                continue;
            }
            if(FindDuplication(temp, 10) == No)
            {
                printf("    %hd%hd%hd%hd%hd/%hd%hd%hd%hd%hd=%hd\n", temp[0], temp[1], temp[2], temp[3],
                        temp[4], temp[5], temp[6], temp[7], temp[8], temp[9], N);
                flag = true;
            }
        }
        if(flag == false)
        {
            printf("    No such numbers\n");
        }
    }
    return 0;
}
Status FindDuplication(short *temp, short N)
{
    short i, j;
    for(i = 0; i < N - 1; i ++)
    {
        for(j = i + 1; j < N; j ++)
        {
            if(temp[i] == temp[j])
            {
                return Yes;
            }
        }
    }
    return No;
}

 代码2：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
vector<int> n({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 });
vector<int> dividend(5), divisor(5);
vector<int> dd(120), ds(120);
vector<vector<pair<int, int>>> res(98765 / 1234);
int i1 = 0, i2 = 0;
void rst() { i1 = 0; i2 = 0; }	//reset
 
void get_res() {
	for (auto dvD : dd) {
		for (auto dvS : ds) {
			if (dvD % dvS == 0) {
				res[dvD / dvS].push_back({ dvD, dvS });
			}
		}
	}
}
 
void permutation(int count, int dvD, int dvS) {
	if (count < 5) {
		for (int i = 0; i < 5; ++i) {	//递归实现：对两个数组中的数字进行全排列
			if (dividend[i] != -1) {
				int tmp1 = dividend[i], tmp2 = divisor[i];
				dividend[i] = -1;	divisor[i] = -1;
				permutation(count + 1, dvD * 10 + tmp1, dvS * 10 + tmp2);
				dividend[i] = tmp1;	divisor[i] = tmp2;
			}
		}
	}
	else {
		dd[i1++] = dvD;
		ds[i2++] = dvS;
	}
}
 
void sol(int beg, int count) {
	if (count < 5) {
		for (int i = beg; i < 10; ++i) {	//递归实现：从10个数中任意抽取5个数字
			dividend[count] = n[i];
			int tmp = n[i];
			n[i] = -1;
			sol(i + 1, count + 1);
			n[i] = tmp;
		}
	}
	else {	//第一步：把10个数划分成两组，一组被除数（放入数组dividend），一组除数（放入数组divisor）
		int idx = 0;
		for (int i = 0; i < 10; ++i) {
			if (n[i] != -1) divisor[idx++] = n[i];
		}
		permutation(0, 0, 0);	//第二步：对两组数进行全排列，放进两个数组中，dividend->dd, divisor->ds
		get_res();	//第三步：分别从两组全排列中任意挑一个数，进行除法
		rst();
	}
}
 
bool cmp_first(const pair<int, int>& a, const pair<int, int>& b) {
	return a.first > b.first;
}
 
int main() {
	sol(0, 0);
	for (size_t i = 0; i < res.size(); ++i) {
		if (res[i].size()) {
			sort(res[i].begin(), res[i].end(), cmp_first);	//对最终结果进行排序
		}
	}
 
	int cnt = 0;
	int N;
	while (cin >> N) {
		cout << "Case " << ++cnt << ":" << endl;
		if (res[N].size()) {
			for (auto d_s : res[N]) {
				printf("    %05d/%05d=%d\n", d_s.first, d_s.second, N);
			}
		}
		else cout << "    No such numbers" << endl;
	}
}

原网站

版权声明
本文为[水w]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_45956730/article/details/125873735

边栏推荐

猜你喜欢

随机推荐