54.简单题？ - 图1

题目概述

题目详情(点我)

有一个1~n（1<=n<=100）的集合 ，现在可以让你在集合中选择任意多个数去减去一个正整数x(x是任意数)，问最少需要操作多少次可以使这个集合中的数都变为0

输入:
输入一个数n(1<=100)，表示集合中的数据数量

输出:
输出最少的操作数

题解

解题方法

  • 找规律
  • 二进制运算

算法知识

  • 数学知识

    • 时间复杂度: 1
    • 空间复杂度: 1

解题思路

审题

  • int n : 1-n个数
  • 可以对任意多的数减去x(任意数)

题目要求

  • 集合中的数全为0需要的最少次操作

思路

  • 要想获得最小的操作，需要满足

    • 减的数尽可能影响更多的数
    • 减完后让尽可能多的数有相同的特点

  • 思路1：找规律

    • 通过样例(n=1), (n=2), (n=3), (n=4), (n=8)得知

      • 只要2^i > n, 则这个i就是最小的操作数, i取最小值
      • 如:
        n = 1, 2^1 > n, 所以最小操作数为1
        n = 2, 2^2 > n, 所以最小操作数为2
        n = 4, 2^3 > n, 所以最小操作数为3
        ….

  • 思路2：二进制计算

    • 对于n = 7来说, 它的二进制为: 111, 则需要的最小操作数为3
    • 对于n = 8来说, 它的二进制为: 1000, 则需要的最小操作数为4

    • 原因:

      • 从最高位开始, 每次减去2^(最高位-1)的值, 这样就可以保证减了后的数与其他的数有共同的特点。而减去的数会影响到所有的当前位上为1的数。
    • 栗子：看下图 54.简单题？ - 图2