65.9K
CodeProject 正在变化。 阅读更多。
Home

查找第一个可被给定数 n 整除的数 (扩展方法)

Nour Helal
starIconstarIconstarIconstarIconstarIcon

5.00/5 (1投票)

2018年7月15日

CPOL

9分钟阅读

viewsIcon

10074

downloadIcon

100

查找第一个可被给定数 n 整除的数 (扩展方法)

目录

简介

您可能已经解决了基本问题，即查找第一个可被给定数 n 整除的数 k，例如

input:
12
37
15

output:
2
37
5

我猜您也通过从 1 开始顺序迭代直到找到满足唯一条件的数 k 来解决了这个问题。

但是，假设问题陈述中有更多条件，例如我说：查找第一个可被 n 整除且其十进制表示仅由零和一组成的数 k。而且，输入 n 的上限约为 10^30，时间限制约为 10 秒，例如

input:
17
25
134
45618735

output:
11101
100
11010110
1011000100000110110110110

近观

当我们将上述约束添加到简单问题的陈述中时，它就变成了一个带有棘手之处的新问题……

首先，您可能会注意到，“仅零和一”的约束使问题变得更大，因为如果您选择迭代直到找到数 k，您将需要检查每个数 x，其数字 x[i] 是否为零、一或都不是，这使得计算更加复杂。

关于输入大小的第二个约束使得无法通过正常迭代解决此问题……正如您所见，输入大小是一个非常大的数字，要找到满足这些约束的数 k，输出将达到大约 10^100 的上限，并且据您所知，这个数字比宇宙中的原子数量还要大得多，并且任何人类制造的内存都无法容纳如此大的数字。

因此，显然我们需要一种新技术来解决这个障碍。

如何解决

1. 时间问题

通过迭代，您必须检查 1 和 k 之间的所有数字，看它们的所有数字是否都是零和一。这会浪费大量时间。但是，有更好的方法。

在 1 和 1000 之间，只有 8 个数字满足第一个条件，它们是 {1,10,11,100,101,110,111,1000}，所以我们不必迭代 1000 个数字，而只需关注 8 个数字，因此我们必须找到一种方法来生成这些数字而不关心其余不相关的数字。对于这个解决方案，我们可以这样做……

从数字 k=1 开始
每次，将 k 乘以 10，然后一次加上 0，另一次加上 1
重复步骤 2 直到找到所需的数字
因此，可以通过递归实现这一点，如下所示……

long long K=1; //The Initial Number We Will Start Searching With
long long wanted_number=10111010100; //The Number We Are Looking For
long long eps=1e15; //Big Number to Stop Recursion

bool find_binary_number(long long x=k){
    Cout<<x<<'\n'; //just to see the progress of generating
    if(x==wanted_number)
        return true;
    if(x>eps)
        return false;
    if(find_binary_number(x*10+0)) //(1)
        return true;
    if(find_binary_number(x*10+1)) //(2)
        return true;
}
前面的代码将生成以下树

Notice
  • 前面的代码是一个原型，展示了思路，在最终代码中会进行更改。
  • 变量 eps 是一个很大的数字，定义为生成限制，如果没有它，递归将继续生成无限数量的集合并导致溢出。
  • 语句 1 和 2 包含 if 语句，在每次函数调用时检查调用函数的最终结果是否为真。我们无法像这样在没有 if 语句的情况下实现它……
find_binary_number(x*10+0);

因为它将调用函数并忽略其结果，并且如果函数满足停止条件，则会停止，而不会关心结果是 true 还是 false。

也不能这样实现……

return find_binary_number(x*10+0);

因为它会在递归的任何分支达到第一个 return 语句后立即退出函数，而不会继续生成。

通过这种方法，我们生成了唯一感兴趣的数字，并减少了消耗时间的无关迭代次数。

2. 输入量巨大

如您所知，C++ 中最大的数据类型是 long double，它的大小为 16 字节，可以存储大约 38 位数字，这仍然离我们的目标大小很远。

因此，您可以使用其他语言，如 Python 或 Java ，它们有其他实现可以存储更大的数字。

但是，如果您想在 C/C++ 中解决此问题，则绝对需要实现另一种数据类型来存储我们想要的内容。

我们可以使用数组方法的相同思想来存储数字的单个数字，以存储更大的数字，并将其与前面的技术结合起来。

我们可以这样做

  1. 创建一个列表来存储每个单独的数字（仅零和一）
  2. 生成零和一个，并将每个数字与列表中当前数字的父数字的索引结合起来
  3. 将新元素插入列表
  4. 重复步骤 2 和 3 特定次数

我们可以这样实现上述技术……

struct state{ //struct represents an element
    int parent; 
    bool digit;
    state(int p, bool d){ //constructor
        parent=p;
        digit=d;
    }
};

vector<state> my_numbers; //list to store the digits

void generate_my_binary_numbers(int number_of_iteration=100){
    state initial_number(-1,1); //initial element
    my_numbers.push_back(initial_number);
    for(int i=0; i<number_of_iteration; ++i)
        for(int j=0; j<2; ++j){
            state new_state(i,j);
            my_numbers.push_back(new_state);
        }
}
Notice
  • 前面的代码是一个原型，展示了思路，在最终代码中会进行更改。
  • 此代码生成的数字在没有将它们组合在一起形成一个数字的情况下没有任何意义，它不是为了生成特定数字，只是一个二进制数字流，我们稍后会组合它们。
  • 变量 parent 表示当前数字在列表中的父数字的索引，因此很容易跟踪任何数字的所有数字。
  • 我们在列表中插入了一个初始元素，digit=1，没有插入 0，因为左边的零没有意义，并且 parent=-1 表示这是第一个元素，没有父数字。

前面的代码将生成这样的列表……

current index:    0  1  2  3  4  5  6  7  8  9 10
digit        :    1  0  1  0  1  0  1  0  1  0  1
parent index :    -1 0  0  1  1  2  2  3  3  4  4

所以，如果我们想从这个列表中生成一个数字，我们所要做的就是跟踪每个数字的父数字，直到我们到达根数字。

因此，如果我们想生成最后一个数字是索引 10 处的数字，我们这样做

  1. 从所需数字的索引开始
  2. 检查此元素是否是最后一个元素
    • 如果是：从本次函数调用返回
    • 如果否：使用当前元素的父索引作为参数再次调用此函数
  3. 打印当前数字

3.打印输出

3.1. 递归法

void get_parent_digit_by_recursion(int x){
    if(x==-1) //reached the last element
       return;
    get_parent_digit_by_recursion(my_numbers[x].parent);
    cout<<my_numbers[x].digit;
}
Notice
  • 我们选择在此函数中使用递归，以便以正确的顺序打印数字，因为我们是反向存储的。
  • 由于 C++ 中的调用堆栈大小有限，此递归可能导致溢出，因为我们需要打印大量数字。
  • 我们可以通过使用我们自己的堆栈并模拟递归过程来解决溢出问题，如下所示……

3.2. 堆栈法

void get_parent_digit_by_stack(int x){
    stack<bool>stk;
    while(x!=-1){
        stk.push(my_numbers[x].digit);
        x=my_numbers[x].parent;
    }
    while(stk.size()){
        cout<<stk.top();
        stk.pop();
    }
}
  • 我们无法使用队列，因为正如我们之前提到的，我们希望以正确的顺序打印数字。
  • 我们也可以使用列表代替堆栈。

4.如何检查 - 数学解决方案 -

现在，我们已经解决了之前提到的所有问题，但是由于使用了这种技术，我们遇到了另一个问题……

如果我们想检查一个数 k 是否可被一个数 n 整除，我们可以轻松地使用……

if((k%n)==0)
    cout<<"It's divisible"<<endl;
else cout<<"It's not divisible";

但由于我们存储的是分离的数字，所以我们做不到。

也许您会想：为什么我不组合我生成的每个数字的数字并检查它是否可整除呢？！

这将是一种灾难性的技术，因为我们使用前面的技术来减少时间，而这种方法将适得其反。

但幸运的是，我们可以使用数论中关于模运算的数学事实，它说明

a mod n = (a mod n) mod n

我们可以将此事实扩展到

<code> </code>b mod n = ((a mod n)*10^k+c) mod n

由于模运算只关心除法的余数，我们可以用数字 a 的模结果来表示数字 b。

55  mod 13 = 3
158 mod 13 = 2
158 mod 13 = (55 * 10^0 + 103) mod 13 = 2 
158 mod 13 = ((55 mod 13) * 10^0 + 103) mod 13 = 2 
As 158 = 55 * 10^0 + 103   &&   55 mod 13 = (55 mod 13) mod 13 
----------------------------------------------------
21  mod 14 = 7
211 mod 14 = 1
211 mod 14 = (21 * 10^1 +0) mod 14 = 1
211 mod 14 = ((21 mod 14) * 10^1 +0) mod 14 = 1
As 211 = 211 * 10^1 + 0    &&   21 mod 14 = (21 mod 14) mod 14
Notice
  • 项 ((55 mod 13) mod 13) 等同于 (55 mod 13) ，项 (* 10^0 + 102) 仅仅是一种将 55 转换为 157 的方法，所以我们发现……
101  mod 23 = 9
1011 mod 23 = 22
1011 mod 23 = (101 * 10^1 + 1) mod 23 = 22
1011 mod 23 = ((101 mod 23) * 10^1 + 1) mod 23 = 22
As 1011 = 101 * 10^1 + 1   &&   1011 mod 23 = (1011 mod 23) mod 23

因此，我们现在可以轻松地解决这个问题，如下所示……

  1. 为每个元素添加一个新字段 mod，存储到目前为止的数字的模结果。
  2. 从列表中的初始元素开始，变量为 digit=1，并存储值 1%n。
  3. 生成下一个两个数字（0,1），并使用前一个元素的 mod 值生成新值。
  4. 对所有后续元素重复步骤 3。

5. 最终代码

上述方法的实现将是

struct state{ //struct represents an element
    int parent;
    bool digit;
    int mod;
    state(int p, bool d,int m){ //constructor
        parent=p;
        digit=d;
        mod=m;
    }
};

vector<state> my_numbers; //list to store the digits

//we chose the stack approach to avoid stack overflow
void get_parent_digit_by_stack(int x){
    stack<bool>stk;
    while(x!=-1){
        stk.push(my_numbers[x].digit);
        x=my_numbers[x].parent;
    }
    while(stk.size()){
        cout<<stk.top();
        stk.pop();
    }
}

void find_my_binary_numbers(int n){
    state initial_state(-1,1,1%n); //initial element
    my_numbers.push_back(initial_state);
    for(int i=0; ; ++i){
       state current_state=my_numbers[i];
       for(int j=0; j<2; ++j){
           state new_state(i,j,(current_state.mod*10+j)%n);
           my_numbers.push_back(new_state);
           if(new_state.mod==0){
               get_parent_digit_by_stack(my_numbers.size()-1);
               return;  
           }
       }
    }
}
前面的代码将生成以下树

Notice
  • 第一个循环没有停止条件，因为我们不知道数字 k 何时会出现。
  • 我们将函数 print_my_number 称为列表中的最后一个索引作为参数，因为我们知道目标元素是存储的最后一个元素。
  • 我们将目标元素的索引发送给 print_my_number 函数，以便跟踪其前面的数字并打印它们，而忽略其余数字。

复杂度分析

通过上述技术，我们在很大程度上降低了时间复杂度。

优化前

假设我们可以通过常规迭代解决问题，那么复杂度将是……

时间复杂度

  • 迭代的 big-O(k)
  • 对于每次迭代，您都需要检查其数字是否为二进制…… big-O(log(k))

优化后

时间复杂度

  • 由于我们只迭代生成数字，所以迭代的复杂度将是 big-O(log(k))。
  • 组合和打印数字的 big-O(log(k))。

由于 k 是一个非常大的数字，高达 10^100，big-O(k) 是一个非常非常糟糕的复杂度，但 big-O(log(k)) 只有 100。

缺点

通过上述方法，我们得以克服许多障碍解决了问题，但我们的解决方案只有一个问题。

由于每次迭代都会生成两个额外的数字，因此生成的数字数量呈指数级增长，因此要达到数字 k，我们需要生成 2^[log(k)+1] 个元素。

想象一下这个数字有多大，如果程序达到 28 位数字，它将生成 536870912 个元素，并且每个元素不仅仅是一个整数，它是一个包含三种不同数据类型的结构，大约 9 字节，因此，内存将立即被填满。

© . All rights reserved.