PTA 7-45 找完数
我写了一个与样例一样的输出结果，但是无法通过检测。希望有朋友可以为我解惑。 首先是让你去写算法你这种叫打表，理论也可以，但是实际违反了练习的本质
而且你需要手动打表出来1-10000的所有内容，所以还是推荐用代码写出来
其次，这个Easy题，稍微思考一下就能秒的垃圾题
# FBI WARNING
装逼版秒法,数据范围内低时间复杂度，纯对答案编程，请勿正式场合玩
```
6= 1 + 2 + 3
28= 1 + 2 + 4 + 7 + 14
```
很容易想到进制方面，查表可知
!(data/attachment/forum/202403/21/072756ohn4nz7t46nx94de.png)
然后查一下奇完数
!(data/attachment/forum/202403/21/072806zo62k916k11q16sk.png)
所以可以直接通过进制判断
设检测8128，我们应判断最低有效位以下是否为全0
最低有效位以上是否为全1
获取最低有效位是x-x&(x-1)，可以获得最低位为64
获取后续为全1可以通过二进制的下滑特性，将64-1，得到代码
```js
const baseBinary = x - (x & (x - 1)) - 1;
if (num & (baseBinary - 1 !== 0)) {
return 0;
}
```
然后可以将原数字与baseBinary - 1做或运算，如果符合完数则是满1
接下来可以根据最位末端求log得到位移多少，因为1比0多一位，所以我们可以多位移一次，然后相加低位满1+1来相加判断是否得到原数，完整检查代码
```js
function checkNumber(num) {
const baseBinary = num - (num & (num - 1)) - 1;
if (num & (baseBinary - 1 !== 0)) {
return false;
}
const moveNum = Math.log2(baseBinary + 1);
if ((baseBinary << (moveNum + 1)) + (baseBinary + 1) === num) {
return true;
}
return false;
}
```
如果符合条件就不断除2，可以得出代码
```js
function getRangeNumber(left, right) {
let text = "";
for (let index = left; index <= right; index++) {
if (checkNumber(index) === true) {
let resultList = [];
let result = Math.ceil(index / 2);
while (result !== 1) {
resultList.push(result);
result = Math.ceil(result / 2);
}
text+=`${index} = 1 + ${resultList.reverse().join(' + ')}\n`
}
}
return text;
}
```
结果多了一个120和2016
```
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
120 = 1 + 2 + 4 + 8 + 15 + 30 + 60
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
2016 = 1 + 2 + 4 + 8 + 16 + 32 + 63 + 126 + 252 + 504 + 1008
8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064
```
我们可以在利用检查特性秒
!(data/attachment/forum/202403/21/072901oxqzodomnfo7fmpz.png)
得到代码
```js
let charArray = index.toString().split("");
while (charArray.length !== 1) {
charArray = charArray
.reduce((accumulator, currentValue) => {
return accumulator + parseInt(currentValue);
}, 0)
.toString()
.split("");
}
```
跑一下再看看
```
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064
```
完整JS代码
```js
function checkNumber(num) {
const baseBinary = num - (num & (num - 1)) - 1;
if (num & (baseBinary - 1 !== 0)) {
return false;
}
const moveNum = Math.log2(baseBinary + 1);
if ((baseBinary << (moveNum + 1)) + (baseBinary + 1) === num) {
return true;
}
return false;
}
function getRangeNumber(left, right) {
let text = "";
for (let index = left; index <= right; index++) {
if (checkNumber(index) === true) {
let resultList = [];
let result = Math.ceil(index / 2);
let charArray = index.toString().split("");
while (charArray.length !== 1) {
charArray = charArray
.reduce((accumulator, currentValue) => {
return accumulator + parseInt(currentValue);
}, 0)
.toString()
.split("");
}
while (result !== 1) {
resultList.push(result);
result = Math.ceil(result / 2);
}
if (index === 6 || charArray === '1') {
text += `${index} = 1 + ${resultList.reverse().join(" + ")}\n`;
}
}
}
return text;
}
console.log(getRangeNumber(1, 10000));
```  李恒道 发表于 2024-3-21 07:26
首先是让你去写算法
你这种叫打表，理论也可以，但是实际违反了练习的本质
而且你需要手动打表出来1-10 ...
TQL GGNB
虽然每个字都认识，但是连起来就不认识了
反正GGNB就完事了 李恒道 发表于 2024-3-21 07:26
首先是让你去写算法
你这种叫打表，理论也可以，但是实际违反了练习的本质
而且你需要手动打表出来1-10 ...
好哥哥，手机在论坛交流不甚方便，晚上下班用上电脑再与你交流 steven026 发表于 2024-3-21 08:13
TQL GGNB
虽然每个字都认识，但是连起来就不认识了
反正GGNB就完事了
普解我记着是N方，这个过滤器O1级别，除法logN，时间复杂度N*logN毒打N方
（其实是我觉得普解没意思，特地玩这种进制的骚解法的
ChHN 发表于 2024-3-21 08:15
好哥哥，手机在论坛交流不甚方便，晚上下班用上电脑再与你交流
哥哥竟然不是学生啊
还做算法 李恒道 发表于 2024-3-21 08:24
普解我记着是N方，这个过滤器O1级别，除法logN，时间复杂度N*logN毒打N方
（其实是我觉得普解没意思，特地 ...
范围也就1-1w，直接打表秒了 王一之 发表于 2024-3-21 09:54
范围也就1-1w，直接打表秒了
打表我就没法装逼了！ 让我感到苦恼的点在于，我将"样例"直接通过打表方式输出，但是检测程序甚至"样例"测试代码都不给我通过。简陋的打表代码如下：
```
#include<stdio.h>
int main(void){
int m,n;
scanf("%d %d",&m,&n); printf("6 = 1 + 2 + 3\n28 = 1 + 2 + 4 + 7 + 14");
return 0;
}
```
页:
[1]
2