r******l
发帖数: 10760 | 1 输入一个正整数N，要求输出所有1到N的可能排列，满足任两个相邻的数之和是一个完
全平方数（比如4，9，16，25等等）。如果不存在这种排列就输出无解。 | e****b
发帖数: 25 | 2 你的意思是比如N是 5的话 我们要1，3这个序列吗？
我觉得是不是可以把1 到2N的完全平房数丢到一个vector 然后我们对1，2，到N的序列
做一个递归
比如N是5 那相邻最大和肯定不超过10，那就只有4和9
然后从1开始 找到3，3递归（只用大于3的序列） 然后因为3找不到6 因此就只有1，3
然后接下来就对2做
当然也可以在对3做递归时做个记录 ，所以2找完后到3时发现3已经做过就没必要再找
了 | S******1
发帖数: 216 | 3
拜托问问题能不能至少把题目意思说清楚。。。
【在 r******l 的大作中提到】
: 输入一个正整数N，要求输出所有1到N的可能排列，满足任两个相邻的数之和是一个完
: 全平方数（比如4，9，16，25等等）。如果不存在这种排列就输出无解。
| i********s
发帖数: 22 | 4 考虑把这些数字作为点，两两能否和为平方数为点之间的连通，求一汉密尔顿回路还是
欧拉回路来着 | S******1
发帖数: 216 | 5
32位的话做pre computation,
计算到2^7
1^2 = 1, hashMap.put(1,1)
2^2 = 4, hashMap.put(4, 2)
3^2 = 9, hashMap.put(9, 3)
....
2^7 = 2^14 hashMap.put(2^14, 2^7)
建立一个vector
check => 1^2 + 2^2 = 6, !hashMap.Contains(6) ==> skip
check => 2^2 + 3^2 = 10, !hashMap.Contains(10) ==> skip
check => 3^2 + 4^2 = 25, hashMap.contains(25), record 3, 4
.....
下次直接查表
【在 r******l 的大作中提到】
: 输入一个正整数N，要求输出所有1到N的可能排列，满足任两个相邻的数之和是一个完
: 全平方数（比如4，9，16，25等等）。如果不存在这种排列就输出无解。
| r******l
发帖数: 10760 | 6 就是1到N，N个数，排成一排。要求相邻两个数加起来是一个完全平方数。要求输入一
个N，输出所有满足要求的排列(或者输出无解)。
【在 S******1 的大作中提到】
:
: 32位的话做pre computation,
: 计算到2^7
: 1^2 = 1, hashMap.put(1,1)
: 2^2 = 4, hashMap.put(4, 2)
: 3^2 = 9, hashMap.put(9, 3)
: ....
: 2^7 = 2^14 hashMap.put(2^14, 2^7)
: 建立一个vector
: check => 1^2 + 2^2 = 6, !hashMap.Contains(6) ==> skip
|
|
