CSDN-猜年龄、纸牌三角形、排他平方数

猜年龄

原题链接：https://edu.csdn.net/skill/practice/algorithm-a413078fb6e74644b8c9f6e28896e377/2258

美国数学家维纳(N.Wiener)智力早熟，11岁就上了大学。他曾在1935~1936年应邀来中国清华大学讲学。

一次，他参加某个重要会议，年轻的脸孔引人注目。于是有人询问他的年龄，他回答说：“我年龄的立方是个4位数。我年龄的4次方是个6位数。这10个数字正好包含了从0到9这10个数字，每个都恰好出现1次。”

请你推算一下，他当时到底有多年轻。

提示：

先用/10和把各个位上的数取出来，然后判断是否相等

官方题目是没给代码的，直接给了年龄作为选项于是我们自己写一个

代码语言：c 复制

#include <iostream>
#include <set>

int main() {
	std::set<int>st;
	for (int i = 11; i < 100; i  ) {
		//我的年龄的立方是个四位数
		if (i * i * i > 1000) {
			//我年龄的4次方是个6位数
			if (i * i * i * i > 100000) {
				//这10个数字正好包含了从0到9这10个数字，每个都恰好出现1次
				//把每位数字塞进set中，判断元素个数是否为10
				int tmp = i * i * i * i;
				while (tmp > 0) {
					st.insert(tmp % 10);
					tmp /= 10;
				}
				tmp = i * i * i;
				while (tmp > 0) {
					st.insert(tmp % 10);
					tmp /= 10;
				}
				if (st.size() == 10) {
					std::cout << i << std::endl;
					break;
				}
			}
		}
	}
	return 0;
}

简单粗暴的算法，代码中带了注释，在此不再赘述。

需要注意的是，要及时跳出。

纸牌三角形

原题链接：https://edu.csdn.net/skill/practice/algorithm-aa21244fb1374002acf29ed59bee7978/2391

A, 2, 3, 4, 5, 6, 7, 8, 9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。

下面就是一种排法

代码语言：c 复制

这样的排法可能会有很多。

如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？

以下程序实现了这一功能，请你补全以下空白处内容：

代码语言：c 复制

#include <bits/stdc  .h>
#define ll long long
using namespace std;
int main()
{
    int a[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int res = 0;
    do
    {
        int x1 = a[0]   a[1]   a[2]   a[3];
        int x2 = a[3]   a[4]   a[5]   a[6];
        int x3 = a[6]   a[7]   a[8]   a[0];
        __________________;
    } while (next_permutation(a, a   9));
    cout << res / 3 / 2 << endl;
    return 0;
}

提示：

1、正三角形有三个角，所以一个数字可以在三个角各出现一次，这就相当于旋转。

2、在生活中你照镜子的时候会发现，当你抬起左手时，你会看到镜子中的你会抬起右手。在本题中滤镜前后包括一个正三角形和该正三角形左右位置对称交换后的正三角形

需要用到全排列函数，呈上cplusplus的官方示例

代码语言：c 复制

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints 3);

  std::cout << "The 3! possible permutations with 3 elements:n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << 'n';
  } while ( std::next_permutation(myints,myints 3) );

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << 'n';

  return 0;
}

全排列函数

对于next_permutation函数，其函数原型为：

#include <algorithm>

bool next_permutation(iterator start,iterator end)

当当前序列不存在下一个排列时，函数返回false，否则返回true

代码语言：c 复制

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	vector<int>vec;
	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(3);
	do {
		cout << vec[0] << " " << vec[1] << " " << vec[2] << endl;
	} while (next_permutation(vec.begin(), vec.end()));
	cout << vec[0] << " " << vec[1] << " " << vec[2] << endl;
	return 0;
}

如果使用do...while则会显示所有可能的全排列方法。上面的例子是6种排列。

如果使用while则会省略初识的第一种排列方法。上面的例子将变为5种排列。

全排列函数会考虑数据相同的元素，不会产生完全重复的排列方式。

在跳出循环后，迭代器会回到全排列之前的状态。

回到题目

题中的while就是个全排列。

然后求全排列后的各边长。

划线的部分就是用来判断是否符合条件。

正确答案

代码语言：c 复制

if (x1 == x2 && x2 == x3)
{
   res  ;
}

题目要求避免旋转和翻转之后的重复情况，而题目中循环内没有去重的部分。

因此去重放在了循环外。

cout << res / 3 / 2 << endl;

res是所有可能的排列，没有去重。
三条边两两互换，有三种实际上相同的可能，需要/3。
每条边内，a[0]和a[3]互换，又会出现两种可能，需要/2。排他平方数原题链接：https://edu.csdn.net/skill/practice/algorithm-ef16a8876b2446c0981c5b9cf28f278d/2314 203879 * 203879 = 41566646641 这有什么神奇呢？仔细观察，203879 是个6位数，并且它的每个数位上的数字都是不同的，并且它平方后的所有数位上都不出现组成它自身的数字。具有这样特点的6位数还有一个，请你找出它！再归纳一下筛选要求：

6位正整数。
每个数位上的数字不同。
其平方数的每个数位不含原数字的任何组成数位。

以下程序实现了这一功能，请你补全以下空白处内容：

代码语言：c 复制

#include <iostream>
using namespace std;

int main()
{
    int num[10], flag;
    for (long long i = 123456; i <= 987654; i  )
    {
        long long a = i;
        long long b = i * i;
        memset(num, 0, sizeof(num));
        flag = 1;
        while (a)
        {
            _________________;
        }
        if (flag)
        {
            while (b)
            {
                if (num[b % 10])
                {
                    flag = 0;
                    break;
                }
                b /= 10;
            }
            if (flag)
                cout << i << endl;
        }
    }
    return 0;
}

正确答案

代码语言：c 复制

if (num[a % 10])
{
    flag = 0;
    break;
}
num[a % 10]  ;
a /= 10;

逐行分析一下

for (long long i = 123456; i <= 987654; i )

题目要求六位数的各位都不相同。

循环从符合条件的最小六位数123456遍历到最大六位数987654。

long long a = i;

long long b = i * i;

分别定义a、b两个变量来存储该六位数和该六位数的平方。

memset(num, 0, sizeof(num));

将循环外定义的数组的内存数据设置为0，用于存储整型各位上的值。

flag = 1;

初始化一个标记，默认值为1。用于在之后的函数中判断走向。如果后面的函数中发现不符合条件，则赋值为0，并执行flag==0时的语句。

while (a)内的语句。

取a的最后一位，并砍掉a的最后一位，修改num数组中存储的个数。

如果添加时发现已存储的个数大于0，说明不符合“不重复”的条件，可以直接跳出循环，同时修改flag标记，快速跳出后面的语句。

如果检测到a已经为0，则跳出循环，执行后面的语句。

if (flag)

flag作为循环条件。是因为上一步的break只能跳出所在的最内层while循环。不符合条件不能直接跳两层，所以使用flag快速跳出。

while (b)

与while(a)语句类似，但删掉了num[a % 10] ;语句，是因为题干没有要求平方后的数值内部不能有重复。只需要比较b的各位上的数不与a重复即可。

如果不符合条件，则修改标记flag等于0。

if (flag)

前面的每一步中，每有不符合条件的情况，都会修改标记为0。

到这一步时，如果flag值为1，说明符合条件，则输出对应的i值。

sdn include iterator permutation

0 人点赞