前端之家

  1. 首页
  2. 问答

给定整数N。大于N且仅以0或1为数字的最小整数是什么？

• 问答

我有一个整数N。我必须找到大于N的最小整数，该整数不包含0或1之外的任何数字。例如：如果N = 12，则答案为100 。 我已经用C ++编写了一种蛮力方法。 

int main() {
    long long n;
    cin >> n;

    for (long long i = n + 1; ; i++) {
        long long temp = i;
        bool ok = true;
        while (temp != 0) {
            if ( (temp % 10) != 0 && (temp % 10) != 1) {
                ok = false;
                break;
            }
            temp /= 10;
        }
        if (ok == true) {
            cout << i << endl;
            break;
        }
    }
}

问题是，我的方法太慢了。我相信有一个非常有效的方法可以解决这个问题。如何有效解决此问题？

sdafffffffffffffff85 回答：给定整数N。大于N且仅以0或1为数字的最小整数是什么？

  1. 增量N，

  2. 从左侧开始扫描，直到找到大于1的数字为止。递增部分数字，然后将其余部分归零。

例如

12 -> 13 -> 1|3 -> 10|0
101 -> 102 -> 10|2 -> 11|0
109 -> 110 -> 110|
111 -> 112 -> 11|2 -> 100|0
198 -> 199 -> 1|99 -> 10|00
1098 -> 1099 -> 10|99 -> 11|00
10203 -> 10204 -> 10|204 -> 11|000
111234 -> 111235 -> 111|235 -> 1000|000
...

证明：

请求的数字必须至少为N + 1，这就是我们递增的原因。我们现在正在寻找一个更大或相等的数字。

让我们将前缀称为开头的0/1数字，后跟后缀。我们必须将后缀的第一位替换为零，并设置较大的前缀。合适的最小前缀是当前前缀加1。而适合的最小后缀是全零。

更新：

我忘记指定前缀必须以二进制数字的形式递增 ，否则会出现禁止的数字。

,

另一种可能性是以下可能性：

  • 您从所使用的数据类型支持的最大的十进制数字“ 1111111 ... 1111”开始

    该算法假定输入小于此数字；否则，您将不得不使用其他数据类型。

    示例：使用long long时，您要以数字1111111111111111111开头。

  • 然后从左到右处理每个十进制数字：
    • 尝试将数字从1更改为0。
    • 如果结果仍然大于输入值，请进行更改（将数字更改为0）。
    • 否则数字仍为1。

示例 

Input = 10103
Start:  111111
Step 1: [1]11111,try [0]11111; 011111 > 10103 => 011111 
Step 2: 0[1]1111,try 0[0]1111; 001111 < 10103 => 011111
Step 3: 01[1]111,try 01[0]111; 010111 > 10103 => 010111
Step 4: 010[1]11,try 010[0]11; 010011 < 10103 => 010111
Step 5: 0101[1]1,try 0101[0]1; 010101 < 10103 => 010111
Step 6: 01011[1],try 01011[0]; 010110 > 10103 => 010110
Result: 010110

正确性证明：

在此算法中，我们逐位处理。在每个步骤中，都有其值已知的数字和尚不知道其值的数字。

在每个步骤中，我们探查最左边的未知数字。

我们将该数字设置为“ 0”，并将所有其他未知数字设置为“ 1”。因为要探测的数字是未知数字中的最高位，所以结果数字是最大可能数字，该数字为“ 0”。如果此数字小于或等于输入，则所探查的数字必须为“ 1”。

另一方面，所得到的数字小于要探查的数字为“ 1”的所有可能的数字。如果结果数字大于输入的数字，则该数字必须为“ 0”。

这意味着我们可以在每一步中计算一位。

C代码

（C代码也应在C ++下工作）：

long long input;
long long result;
long long digit;

... read in input ...

result = 1111111111111111111ll;
digit = 1000000000000000000ll;

while( digit > 0 )
{
    if(result - digit > input)
    {
        result -= digit;
    }
    digit /= 10;
}

... print out output ...
,

让我提出一些替代方案。

I。递增。认为它是@YvesDaoust方法的修改。

  1. 将N增加1
  2. 以前导零扩展结果
  3. 从最后一位到第二位
    （a）如果小于2，则保留所有内容
    （b）否则将其设置为0并增加前导
  4. 重复步骤3a，b

示例：

1. N = 0 -> 1 -> (0)|(1) -> 1
2. N = 1 -> 2 -> (0)|(2) -> (1)|(0) -> 10
3. N = 101 -> 102 -> (0)|(1)(0)(2) -> (0)|(1)(1)(0) -> (0)|(1)(1)(0) -> (0)|(1)(1)(0) -> 110
4. N = 298 -> 299 -> (0)|(2)(9)(9) -> (0)|(2)(10)(0) -> (0)|(3)(0)(0) -> (1)|(0)(0)(0) -> 1000

您将获得十进制格式的结果。

II。划分。

  1. 将N增加1
  2. 将总和设置为0
  3. 将结果除以10得到div（D）和mod（M）部分
  4. 检查M
    （a）如果M超过1，则增加D
    （b）否则将总和增加M * 10 k ，其中k是当前迭代次数（从0开始）
  5. 重复步骤3,4，直到D为0

示例1：

1. N = 0 -> N = 1
2. sum = 0
3. 1/10 -> D == 0,M == 1 -> sum = sum + 1*10^0 == 1
4. D == 0 -> sum == 1

示例2：

1. N = 1 -> N = 2
2. sum = 0
3. 2/10 -> D == 0,M == 2 -> D = D + 1 == 1
4. 1/10 -> D == 0,M == 1 -> sum = sum + 1*10^1 == 10
5. D == 0,sum == 10

示例3：

1. N = 101 -> N = 102
2. sum = 0
3. 102/10 -> D == 10,M == 2 -> D = D + 1 == 11
4. 11/10 -> D == 1,M == 1 -> sum = sum + 1*10^1 = 10
5. 1/10 -> D == 0,M == 1 -> sum = sum + 1*10^2 == 10 + 100 == 110
6. D == 0,sum == 110

示例4：

1. N = 298 -> N = 299
2. sum = 0
3. 299/10 -> D == 29,M == 9 -> D = D + 1 == 30
4. 30/10 -> D == 3,M == 0 -> sum = sum + 0*10^1 == 0
5. 3/10 -> D == 0,M == 3 -> D = D + 1
6. 1/10 -> D == 0,M == 1 -> sum = sum + 1*10^3 == 1000
7. D == 0,sum == 1000
algorithmc++
本文链接：https://www.f2er.com/3104269.html

大家都在问