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
|
|