PTA 7-45 找完数

ChHN

我写了一个与样例一样的输出结果，但是无法通过检测。希望有朋友可以为我解惑。

李恒道

首先是让你去写算法
你这种叫打表，理论也可以，但是实际违反了练习的本质
而且你需要手动打表出来1-10000的所有内容，所以还是推荐用代码写出来

其次，这个Easy题，稍微思考一下就能秒的垃圾题

FBI WARNING

装逼版秒法,数据范围内低时间复杂度，纯对答案编程，请勿正式场合玩

6= 1 + 2 + 3
28= 1 + 2 + 4 + 7 + 14

很容易想到进制方面，查表可知

然后查一下奇完数

所以可以直接通过进制判断
设检测8128，我们应判断最低有效位以下是否为全0
最低有效位以上是否为全1
获取最低有效位是x-x&(x-1)，可以获得最低位为64
获取后续为全1可以通过二进制的下滑特性，将64-1，得到代码

  const baseBinary = x - (x & (x - 1)) - 1;
  if (num & (baseBinary - 1 !== 0)) {
    return 0;
  }

然后可以将原数字与baseBinary - 1做或运算，如果符合完数则是满1

接下来可以根据最位末端求log得到位移多少，因为1比0多一位，所以我们可以多位移一次，然后相加低位满1+1来相加判断是否得到原数，完整检查代码

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，可以得出代码

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

我们可以在利用检查特性秒

得到代码

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

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[0] === '1') {
        text += `${index} = 1 + ${resultList.reverse().join(" + ")}\n`;
      }
    }
  }
  return text;
}
console.log(getRangeNumber(1, 10000));

李恒道

steven026

李恒道 发表于 2024-3-21 07:26
[md]首先是让你去写算法
你这种叫打表，理论也可以，但是实际违反了练习的本质
而且你需要手动打表出来1-10 ...

TQL GGNB
虽然每个字都认识，但是连起来就不认识了
反正GGNB就完事了

ChHN

李恒道 发表于 2024-3-21 07:26
[md]首先是让你去写算法
你这种叫打表，理论也可以，但是实际违反了练习的本质
而且你需要手动打表出来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，直接打表秒了

打表我就没法装逼了！

ChHN

让我感到苦恼的点在于，我将"样例"直接通过打表方式输出，但是检测程序甚至"样例"测试代码都不给我通过。简陋的打表代码如下：

#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;
}