精华内容
下载资源
问答
  • 数论之模加法运算

    千次阅读 2017-04-12 21:16:10
    问题一个mm位的整数,有多少可以...数论中的模加法运算有这样的性质(对乘法也是一样):(a+b) mod n===(a mod n+b mod n) mod n(a mod n+b) mod n(a+b mod n) mod n \begin{array}{lcl} (a+b)\ \text

    问题

    一个m位的整数,有多少可以被整数n整除?其中m可以大于15。

    • 测试输入
      1 3
    • 测试输出
      4

    分析1

    这个问题显然不能穷举所有的情况。数论中的模加法运算有这样的性质(对乘法也是一样):

    (a+b) mod n===(a mod n+b mod n) mod n(a mod n+b) mod n(a+b mod n) mod n

    由此可见,一个数的取模问题可以拆分成两个求和数的取模问题,这显然属于动态规划能够解决的问题。对于一个m位的整数x,可以将其按照十进制拆解为x=x0×10m1+x1×10m2++xm2×10+xm1。对于其中的i1i位做如下分析:
    j=xi1 mod n,则

    (xi1×10+xi) mod n====[(xi1×10) mod n+xi] mod n{[(xi1 mod n)×10] mod n+xi} mod n[(j×10) mod n+xi] mod n(j×10+xi) mod n

    由此定义c[i,j]为前i位数模n余数为j的个数,原问题为c[m,0]。第i位的取值k=09,穷举一遍后前i位余数为(j10+k)%n的个数,等于前i1位余数为j的个数的累计和。从而递归式为

    {c[0,0]=1,c[i,j]=0,c[i,(j10+k)%n] +=c[i1,j],i=0,j0i0,k=09

    代码1

    import java.util.Scanner;
    
    public class ModNums {
        static void solution(long[][] c, int m, int n) {
            for (int i = 0; i < n; i++) {
                c[0][i] = 0L;
            }
            c[0][0] = 1L;
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < 10; k++) {
                        c[i][(j * 10 + k) % n] += c[i - 1][j];
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int m = sc.nextInt();
            int n = sc.nextInt();
            long[][] c = new long[m + 1][n];
            solution(c, m, n);
            System.out.println(c[m][0]);
        }
    }

    变形

    一个m位的整数,其中有某些位不确定,用”X”表示,有多少可以被整数n整除?

    • 测试输入
      999999999X 3
    • 测试输出
      4

    分析2

    整体和原问题一样,只是不确定的位才需要穷举一遍,确定的位直接更新即可。

    代码2

    import java.util.Scanner;
    
    public class AmbiguousNums {
        static void solution(long[][] c, String seq, int n) {
            int length = seq.length();
            for (int i = 0; i < n; i++) {
                c[0][i] = 0L;
            }
            c[0][0] = 1L;
            for (int i = 1; i <= length; i++) {
                char ch = seq.charAt(i - 1);
                for (int j = 0; j < n; j++) {
                    if (ch == 'X') {
                        for (int k = 0; k < 10; k++) {
                            c[i][(j * 10 + k) % n] += c[i - 1][j];
                        }
                    } else {
                        int k = ch - '0';
                        c[i][(j * 10 + k) % n] += c[i - 1][j];
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String seq = sc.next();
            int length = seq.length();
            int n = sc.nextInt();
            long[][] c = new long[length + 1][n];
            solution(c, seq, n);
            System.out.println(c[length][0]);
        }
    }
    展开全文
  • 为了能利用深度学习模型模拟整数的加法运算,我们需要将输入的两个加数和输出的结果用二进制表示,这样就能得到向量,如加数在0-255内,可以用8位0-1向量来表示,前面的空位用0填充;结果在0-510内,可以用9位0-1...

      本文将介绍LSTM模型在实现整数加法方面的应用。
      我们以0-255之间的整数加法为例,生成的结果在0到510之间。为了能利用深度学习模型模拟整数的加法运算,我们需要将输入的两个加数和输出的结果用二进制表示,这样就能得到向量,如加数在0-255内,可以用8位0-1向量来表示,前面的空位用0填充;结果在0-510内,可以用9位0-1向量来表示,前面的空位用0填充。因为两个加数均在0-255内变化,所以共有256*256=65536个输入向量以及65536个输出向量,输入向量为两个加数的二进制向量的拼接结果,因而是个16为的输入向量。用以下的Python代码可以模拟以上过程:

    import numpy as np
    
    # 最多8位二进制
    BINARY_DIM = 8
    
    # 将整数表示成为binary_dim位的二进制数,高位用0补齐
    def int_2_binary(number, binary_dim):
        binary_list = list(map(lambda x: int(x), bin(number)[2:]))
        number_dim = len(binary_list)
        result_list = [0]*(binary_dim-number_dim)+binary_list
        return result_list
    
    # 将一个二进制数组转为整数
    def binary2int(binary_array):
        out = 0
        for index, x in enumerate(reversed(binary_array)):
            out += x * pow(2, index)
        return out
    
    # 将[0,2**BINARY_DIM)所有数表示成二进制
    binary = np.array([int_2_binary(x, BINARY_DIM) for x in range(2**BINARY_DIM)])
    # print(binary)
    
    # 样本的输入向量和输出向量
    dataX = []
    dataY = []
    for i in range(binary.shape[0]):
        for j in range(binary.shape[0]):
            dataX.append(np.append(binary[i], binary[j]))
            dataY.append(int_2_binary(i+j, BINARY_DIM+1))
    
    # print(dataX)
    # print(dataY)
    
    # 重新特征X和目标变量Y数组,适应LSTM模型的输入和输出
    X = np.reshape(dataX, (len(dataX), 2*BINARY_DIM, 1))
    # print(X.shape)
    Y = np.array(dataY)
    # print(dataY.shape)

    在以上代码中,得到的dataX和dataY以满足要求,但为了能让LSTM模型处理,需要改变这两个数据集的形状。
      我们采用LSTM模型来训练上述数据,LSTM模型的结构很简单,就是简单的一层LSTM层,然后加上Dropout层,最后是全连接层,激活函数采用sigmoid函数,采用的损失函数为平均平方误差。整个结构的示意图如下:

    LSTM模型的结构示意图

    模型训练的代码如下:

    from keras.models import Sequential
    from keras.layers import Dense
    from keras.layers import Dropout
    from keras.layers import LSTM
    from keras import losses
    from keras.utils import plot_model
    
    # 定义LSTM模型
    model = Sequential()
    model.add(LSTM(256, input_shape=(X.shape[1], X.shape[2])))
    model.add(Dropout(0.2))
    model.add(Dense(Y.shape[1], activation='sigmoid'))
    model.compile(loss=losses.mean_squared_error, optimizer='adam')
    # print(model.summary())
    
    # plot model
    plot_model(model, to_file=r'./model.png', show_shapes=True)
    # train model
    epochs = 100
    model.fit(X, Y, epochs=epochs, batch_size=128)
    # save model
    mp = r'./LSTM_Operation.h5'
    model.save(mp)

    该LSTM模型每批训练128个样本,共训练100次,采用Adam优化器减少损失值。
      对这个模型进行训练,训练100次,损失值为0.0045。接下来我们就要用这个训练好的模型来预测。我们预测的方法为,虽然挑两个在0-255内的加数,转化为二进制向量作为输入向量,然后由LSTM模型输出结果,将该结果取整作为输出向量中的元素,最后将这个输出向量转化为整数,就是预测的两个加数的和。模型预测的代码如下:

    # use LSTM model to predict
    for _ in range(100):
        start = np.random.randint(0, len(dataX)-1)
        # print(dataX[start])
        number1 = dataX[start][0:BINARY_DIM]
        number2 = dataX[start][BINARY_DIM:]
        print('='*30)
        print('%s: %s'%(number1, binary2int(number1)))
        print('%s: %s'%(number2, binary2int(number2)))
        sample = np.reshape(X[start], (1, 2*BINARY_DIM, 1))
        predict = np.round(model.predict(sample), 0).astype(np.int32)[0]
        print('%s: %s'%(predict, binary2int(predict)))

    预测的100组样本的输出结果如下:

    ==============================
    [1 0 0 1 1 1 0 1]: 157
    [0 1 1 1 0 0 0 1]: 113
    [1 0 0 0 0 1 1 1 0]: 270
    ==============================
    [1 1 1 0 1 0 1 0]: 234
    [0 1 0 0 1 1 0 0]: 76
    [1 0 0 1 1 0 1 1 0]: 310
    ==============================
    [1 1 0 0 0 1 0 0]: 196
    [1 1 0 1 1 0 1 1]: 219
    [1 1 0 0 1 1 1 1 1]: 415
    ==============================
    [0 0 1 1 1 0 1 0]: 58
    [0 0 1 0 0 0 1 1]: 35
    [0 0 1 0 1 1 1 0 1]: 93
    ==============================
    [1 0 0 0 0 0 0 0]: 128
    [0 1 1 1 1 0 0 1]: 121
    [0 1 1 1 1 1 0 0 1]: 249
    ==============================
    [1 1 1 1 0 1 1 0]: 246
    [1 1 0 1 0 1 0 1]: 213
    [1 1 1 0 0 1 0 1 1]: 459
    ==============================
    [1 1 1 0 0 1 1 0]: 230
    [1 0 0 0 0 0 0 0]: 128
    [1 0 1 1 0 0 1 1 0]: 358
    ==============================
    [1 0 1 0 0 0 1 1]: 163
    [0 1 1 0 0 1 0 1]: 101
    [1 0 0 0 0 1 0 0 0]: 264
    ==============================
    [1 0 1 0 0 1 1 0]: 166
    [0 1 0 1 0 0 0 0]: 80
    [0 1 1 1 1 0 1 1 0]: 246
    ==============================
    [0 0 0 0 1 0 1 1]: 11
    [0 1 0 0 0 1 0 1]: 69
    [0 0 1 0 1 0 0 0 0]: 80
    ==============================
    [1 1 1 1 0 1 1 1]: 247
    [0 1 1 1 0 0 0 0]: 112
    [1 0 1 1 0 0 1 1 1]: 359
    ==============================
    [1 0 1 0 1 0 0 1]: 169
    [1 1 0 0 0 0 0 0]: 192
    [1 0 1 1 0 1 0 0 1]: 361
    ==============================
    [1 0 1 1 0 0 0 1]: 177
    [1 0 0 0 1 0 1 1]: 139
    [1 0 0 1 1 1 1 0 0]: 316
    ==============================
    [0 1 0 0 0 1 1 0]: 70
    [0 0 1 0 1 1 1 0]: 46
    [0 0 1 1 1 0 1 0 0]: 116
    ==============================
    [1 0 0 1 1 0 1 1]: 155
    [1 1 0 0 0 0 0 1]: 193
    [1 0 1 0 1 1 1 0 0]: 348
    ==============================
    [1 0 1 1 0 0 1 0]: 178
    [1 0 0 0 1 1 1 1]: 143
    [1 0 1 0 0 0 0 0 1]: 321
    ==============================
    [0 1 0 1 1 1 1 1]: 95
    [1 1 1 0 0 1 0 0]: 228
    [1 0 1 0 0 0 0 1 1]: 323
    ==============================
    [1 0 0 1 1 1 1 0]: 158
    [0 0 0 1 1 0 0 1]: 25
    [0 1 0 1 1 0 1 1 1]: 183
    ==============================
    [1 1 1 0 1 0 1 1]: 235
    [1 1 0 0 0 0 0 1]: 193
    [1 1 0 1 0 1 1 0 0]: 428
    ==============================
    [0 1 0 1 1 1 0 1]: 93
    [0 1 1 1 0 1 1 0]: 118
    [0 1 1 0 1 0 0 1 1]: 211
    ==============================
    [1 1 1 1 1 1 1 1]: 255
    [1 1 1 1 1 1 1 0]: 254
    [1 1 1 1 1 1 1 0 1]: 509
    ==============================
    [0 1 0 1 1 0 0 1]: 89
    [0 1 0 1 1 1 1 0]: 94
    [0 1 0 1 1 0 1 1 1]: 183
    ==============================
    [0 1 1 1 0 0 0 0]: 112
    [0 0 1 1 0 1 0 0]: 52
    [0 1 0 1 0 0 1 0 0]: 164
    ==============================
    [1 0 0 0 0 0 0 0]: 128
    [1 1 0 1 1 0 1 0]: 218
    [1 0 1 0 1 1 0 1 0]: 346
    ==============================
    [0 0 1 1 0 1 0 1]: 53
    [1 0 1 1 1 1 1 0]: 190
    [0 1 1 1 1 0 0 1 1]: 243
    ==============================
    [0 1 1 1 1 0 0 0]: 120
    [1 1 0 1 0 1 0 1]: 213
    [1 0 1 0 0 1 1 0 1]: 333
    ==============================
    [0 1 1 1 1 0 1 1]: 123
    [1 1 1 0 1 1 0 1]: 237
    [1 0 1 1 0 1 0 0 0]: 360
    ==============================
    [1 0 0 1 1 0 1 0]: 154
    [0 1 1 0 1 0 0 1]: 105
    [1 0 0 0 0 0 0 1 1]: 259
    ==============================
    [0 0 0 1 1 0 0 1]: 25
    [0 1 0 1 1 0 1 0]: 90
    [0 0 1 1 1 0 0 1 1]: 115
    ==============================
    [1 1 1 1 0 0 0 1]: 241
    [0 0 0 1 1 1 1 1]: 31
    [1 0 0 0 1 0 0 0 0]: 272
    ==============================
    [0 1 0 0 0 1 1 0]: 70
    [1 1 1 0 1 0 0 1]: 233
    [1 0 0 1 0 1 1 1 1]: 303
    ==============================
    [1 0 1 0 1 1 0 1]: 173
    [0 1 1 1 0 1 0 0]: 116
    [1 0 0 1 0 0 0 0 1]: 289
    ==============================
    [0 1 0 0 1 0 0 0]: 72
    [1 1 1 1 1 0 1 0]: 250
    [1 0 1 0 0 0 0 1 0]: 322
    ==============================
    [1 1 1 1 0 0 0 0]: 240
    [0 1 0 0 0 0 1 0]: 66
    [1 0 0 1 1 0 0 1 0]: 306
    ==============================
    [0 1 0 0 0 1 1 1]: 71
    [1 0 0 1 0 1 1 0]: 150
    [0 1 1 0 1 1 1 0 1]: 221
    ==============================
    [0 1 1 0 1 1 0 1]: 109
    [0 0 1 0 0 1 0 1]: 37
    [0 1 0 0 1 0 0 1 0]: 146
    ==============================
    [1 1 0 0 0 0 0 0]: 192
    [1 1 1 0 0 0 0 1]: 225
    [1 1 0 1 0 0 0 0 1]: 417
    ==============================
    [1 0 0 0 0 0 1 1]: 131
    [1 1 0 1 1 1 1 0]: 222
    [1 0 1 1 0 0 0 0 1]: 353
    ==============================
    [0 0 0 0 0 1 0 0]: 4
    [1 1 1 0 0 0 1 0]: 226
    [0 1 1 1 0 0 1 1 0]: 230
    ==============================
    [1 1 1 0 1 1 1 1]: 239
    [1 1 0 1 1 0 1 1]: 219
    [1 1 1 0 0 1 0 1 0]: 458
    ==============================
    [0 0 1 1 0 1 0 1]: 53
    [1 1 1 1 0 0 1 0]: 242
    [1 0 0 1 0 0 1 1 1]: 295
    ==============================
    [1 0 0 1 0 0 0 1]: 145
    [0 1 0 0 0 1 0 0]: 68
    [0 1 1 0 1 0 1 0 1]: 213
    ==============================
    [0 0 1 1 0 0 0 0]: 48
    [1 0 1 1 0 1 1 1]: 183
    [0 1 1 1 0 0 1 1 1]: 231
    ==============================
    [0 1 1 0 0 1 1 1]: 103
    [0 0 0 1 1 1 1 0]: 30
    [0 1 0 0 0 0 1 0 1]: 133
    ==============================
    [0 1 0 1 1 1 0 1]: 93
    [1 1 0 1 0 0 1 0]: 210
    [1 0 0 1 0 1 1 1 1]: 303
    ==============================
    [1 0 0 0 1 0 1 0]: 138
    [0 1 1 1 1 0 0 1]: 121
    [1 0 0 0 0 0 0 1 1]: 259
    ==============================
    [0 0 0 0 0 0 1 1]: 3
    [0 0 1 1 0 0 0 1]: 49
    [0 0 0 1 1 0 1 0 0]: 52
    ==============================
    [1 0 0 0 0 0 1 0]: 130
    [0 0 0 1 0 0 0 0]: 16
    [0 1 0 0 1 0 0 1 0]: 146
    ==============================
    [0 0 0 1 0 0 0 0]: 16
    [1 0 0 1 0 0 1 0]: 146
    [0 1 0 1 0 0 0 1 0]: 162
    ==============================
    [0 1 0 1 0 1 0 0]: 84
    [0 0 0 0 1 1 0 0]: 12
    [0 0 1 1 0 0 0 0 0]: 96
    ==============================
    [1 0 1 0 1 0 1 1]: 171
    [1 1 0 1 1 0 1 1]: 219
    [1 1 0 0 0 0 1 1 0]: 390
    ==============================
    [1 1 1 1 1 1 1 0]: 254
    [0 1 1 0 1 0 1 0]: 106
    [1 0 1 1 0 1 0 0 0]: 360
    ==============================
    [1 0 0 0 0 0 1 0]: 130
    [0 0 0 0 1 1 1 0]: 14
    [0 1 0 0 1 0 0 0 0]: 144
    ==============================
    [1 0 1 0 0 1 0 1]: 165
    [0 0 1 1 1 0 1 1]: 59
    [0 1 1 1 0 0 0 0 0]: 224
    ==============================
    [0 0 1 1 1 0 1 0]: 58
    [1 1 1 1 0 0 1 0]: 242
    [1 0 0 1 0 1 1 0 0]: 300
    ==============================
    [0 1 0 0 1 1 0 1]: 77
    [0 0 0 1 1 1 1 1]: 31
    [0 0 1 1 0 1 1 0 0]: 108
    ==============================
    [1 0 0 1 1 0 1 0]: 154
    [0 1 0 1 0 1 0 1]: 85
    [0 1 1 1 0 1 1 1 1]: 239
    ==============================
    [0 1 1 0 1 1 0 1]: 109
    [0 1 1 0 1 0 0 1]: 105
    [0 1 1 0 1 0 1 1 0]: 214
    ==============================
    [0 1 1 1 1 1 1 1]: 127
    [0 1 1 1 0 0 1 0]: 114
    [0 1 1 1 1 0 0 0 1]: 241
    ==============================
    [0 1 1 0 0 1 0 1]: 101
    [0 1 0 1 0 0 0 0]: 80
    [0 1 0 1 1 0 1 0 1]: 181
    ==============================
    [0 1 1 0 1 1 1 0]: 110
    [0 1 0 1 0 1 1 0]: 86
    [0 1 1 0 0 0 1 0 0]: 196
    ==============================
    [0 0 0 1 0 0 1 1]: 19
    [1 0 0 1 0 0 0 0]: 144
    [0 1 0 1 0 0 0 1 1]: 163
    ==============================
    [1 1 1 1 0 1 0 0]: 244
    [1 1 0 1 0 0 1 1]: 211
    [1 1 1 0 0 0 1 1 1]: 455
    ==============================
    [0 0 0 0 1 1 1 0]: 14
    [1 0 1 1 0 0 1 0]: 178
    [0 1 1 0 0 0 0 0 0]: 192
    ==============================
    [0 1 1 0 0 0 0 0]: 96
    [1 0 0 1 1 1 0 0]: 156
    [0 1 1 1 1 1 1 0 0]: 252
    ==============================
    [0 0 1 1 0 1 0 0]: 52
    [0 1 1 1 1 1 0 1]: 125
    [0 1 0 1 1 0 0 0 1]: 177
    ==============================
    [0 0 0 0 1 1 0 0]: 12
    [0 1 0 1 1 1 0 1]: 93
    [0 0 1 1 0 1 0 0 1]: 105
    ==============================
    [0 1 1 0 0 1 0 1]: 101
    [1 1 0 1 0 1 0 0]: 212
    [1 0 0 1 1 1 0 0 1]: 313
    ==============================
    [1 1 0 0 0 0 0 1]: 193
    [1 1 0 0 1 1 0 1]: 205
    [1 1 0 0 0 1 1 1 0]: 398
    ==============================
    [0 1 1 1 0 0 1 0]: 114
    [0 0 0 0 0 0 0 0]: 0
    [0 0 1 1 1 0 0 1 0]: 114
    ==============================
    [1 0 0 0 1 1 1 0]: 142
    [1 0 1 1 1 1 0 1]: 189
    [1 0 1 0 0 1 0 1 1]: 331
    ==============================
    [1 0 1 1 0 1 1 1]: 183
    [0 1 0 1 0 1 1 0]: 86
    [1 0 0 0 0 1 1 0 1]: 269
    ==============================
    [1 0 1 0 0 0 1 1]: 163
    [1 1 1 0 0 1 0 1]: 229
    [1 1 0 0 0 1 0 0 0]: 392
    ==============================
    [0 0 1 1 0 0 0 1]: 49
    [1 1 1 0 0 1 1 1]: 231
    [1 0 0 0 1 1 0 0 0]: 280
    ==============================
    [1 0 0 0 1 1 1 1]: 143
    [1 0 1 0 1 0 0 0]: 168
    [1 0 0 1 1 0 1 1 1]: 311
    ==============================
    [0 1 0 0 0 0 0 0]: 64
    [0 0 0 0 0 1 0 1]: 5
    [0 0 1 0 0 0 1 0 1]: 69
    ==============================
    [1 1 1 1 1 0 1 1]: 251
    [1 0 1 1 1 0 0 1]: 185
    [1 1 0 1 1 0 1 0 0]: 436
    ==============================
    [1 1 1 0 1 1 1 0]: 238
    [1 1 0 0 0 0 1 0]: 194
    [1 1 0 1 1 0 0 0 0]: 432
    ==============================
    [0 0 1 1 1 1 0 0]: 60
    [0 0 0 1 0 1 1 1]: 23
    [0 0 1 0 1 0 0 1 1]: 83
    ==============================
    [0 1 1 1 0 1 0 0]: 116
    [1 1 1 1 1 1 0 0]: 252
    [1 0 1 1 1 0 0 0 0]: 368
    ==============================
    [1 1 0 1 0 1 1 0]: 214
    [1 1 1 1 0 1 0 0]: 244
    [1 1 1 0 0 1 0 1 0]: 458
    ==============================
    [1 1 1 1 1 1 1 0]: 254
    [1 1 0 1 0 0 0 1]: 209
    [1 1 1 0 0 1 1 1 1]: 463
    ==============================
    [0 0 0 0 0 0 1 0]: 2
    [0 0 0 0 1 1 0 1]: 13
    [0 0 0 0 0 1 1 1 1]: 15
    ==============================
    [0 1 1 0 0 1 1 1]: 103
    [1 0 1 1 1 1 1 0]: 190
    [1 0 0 1 0 0 1 0 1]: 293
    ==============================
    [1 1 1 1 0 1 1 0]: 246
    [0 1 0 1 0 0 1 0]: 82
    [1 0 1 0 0 1 0 0 0]: 328
    ==============================
    [0 1 1 1 0 0 1 1]: 115
    [0 0 1 1 1 0 1 1]: 59
    [0 1 0 1 0 1 1 1 0]: 174
    ==============================
    [0 1 0 1 1 0 0 1]: 89
    [0 1 1 0 1 0 1 1]: 107
    [0 1 1 0 0 0 1 0 0]: 196
    ==============================
    [0 1 0 0 0 1 0 0]: 68
    [0 0 1 1 1 0 0 0]: 56
    [0 0 1 1 1 1 1 0 0]: 124
    ==============================
    [1 1 0 0 1 0 0 0]: 200
    [1 0 1 0 0 0 1 0]: 162
    [1 0 1 1 0 1 0 1 0]: 362
    ==============================
    [1 1 1 1 0 0 1 1]: 243
    [0 1 1 0 0 0 1 1]: 99
    [1 0 1 0 1 0 1 1 0]: 342
    ==============================
    [0 0 1 0 1 0 0 1]: 41
    [0 1 0 0 1 0 0 1]: 73
    [0 0 1 1 1 0 0 1 0]: 114
    ==============================
    [0 0 0 1 1 1 0 1]: 29
    [1 0 1 0 1 1 1 0]: 174
    [0 1 1 0 0 1 0 1 1]: 203
    ==============================
    [0 0 0 0 1 1 1 1]: 15
    [0 0 1 1 1 1 0 1]: 61
    [0 0 1 0 0 1 1 0 0]: 76
    ==============================
    [1 1 1 1 1 0 1 1]: 251
    [1 1 0 1 0 0 0 0]: 208
    [1 1 1 0 0 1 0 1 1]: 459
    ==============================
    [1 1 1 0 1 0 0 0]: 232
    [0 1 1 0 0 0 1 0]: 98
    [1 0 1 0 0 1 0 1 0]: 330
    ==============================
    [1 0 1 1 0 1 0 0]: 180
    [0 1 0 1 0 1 1 1]: 87
    [1 0 0 0 0 1 0 1 1]: 267
    ==============================
    [1 0 0 0 0 1 1 0]: 134
    [1 0 0 1 0 1 0 1]: 149
    [1 0 0 0 1 1 0 1 1]: 283
    ==============================
    [1 0 1 0 1 1 0 1]: 173
    [0 1 1 1 1 1 0 0]: 124
    [1 0 0 1 0 1 0 0 1]: 297
    ==============================
    [0 1 0 0 1 0 0 0]: 72
    [0 1 1 0 0 0 1 1]: 99
    [0 1 0 1 0 1 0 1 1]: 171
    ==============================
    [1 1 0 1 0 1 0 1]: 213
    [0 0 0 1 1 1 1 0]: 30
    [0 1 1 1 1 0 0 1 1]: 243

      可以看到,这个简单的LSTM模型的预测的结果全部正确。因此,这就可以用来模拟0-255内的整数的加法运算,是不是很神奇呢?
      如果需要想将加数的范围扩大,只需要改变代码中的BINARY_DIM变量即可。但是,加数的范围越大,样本就越大,如2**10=1024内的加法,就会有1024*1024=1048576个样本,这样大的样本量的无疑需要更多的训练时间。
      本文到此结束,感谢阅读~如果不当之处,请速联系笔者,欢迎大家交流~祝您好运~

    注意:本人现已开通微信公众号: Python爬虫与算法(微信号为:easy_web_scrape), 欢迎大家关注哦~~

    完整的Python代码如下:

    import numpy as np
    from keras.models import Sequential
    from keras.layers import Dense
    from keras.layers import Dropout
    from keras.layers import LSTM
    from keras import losses
    from keras.utils import plot_model
    
    # 最多8位二进制
    BINARY_DIM = 8
    
    # 将整数表示成为binary_dim位的二进制数,高位用0补齐
    def int_2_binary(number, binary_dim):
        binary_list = list(map(lambda x: int(x), bin(number)[2:]))
        number_dim = len(binary_list)
        result_list = [0]*(binary_dim-number_dim)+binary_list
        return result_list
    
    # 将一个二进制数组转为整数
    def binary2int(binary_array):
        out = 0
        for index, x in enumerate(reversed(binary_array)):
            out += x * pow(2, index)
        return out
    
    # 将[0,2**BINARY_DIM)所有数表示成二进制
    binary = np.array([int_2_binary(x, BINARY_DIM) for x in range(2**BINARY_DIM)])
    # print(binary)
    
    # 样本的输入向量和输出向量
    dataX = []
    dataY = []
    for i in range(binary.shape[0]):
        for j in range(binary.shape[0]):
            dataX.append(np.append(binary[i], binary[j]))
            dataY.append(int_2_binary(i+j, BINARY_DIM+1))
    
    # print(dataX)
    # print(dataY)
    
    # 重新特征X和目标变量Y数组,适应LSTM模型的输入和输出
    X = np.reshape(dataX, (len(dataX), 2*BINARY_DIM, 1))
    # print(X.shape)
    Y = np.array(dataY)
    # print(dataY.shape)
    
    # 定义LSTM模型
    model = Sequential()
    model.add(LSTM(256, input_shape=(X.shape[1], X.shape[2])))
    model.add(Dropout(0.2))
    model.add(Dense(Y.shape[1], activation='sigmoid'))
    model.compile(loss=losses.mean_squared_error, optimizer='adam')
    # print(model.summary())
    
    # plot model
    plot_model(model, to_file=r'./model.png', show_shapes=True)
    # train model
    epochs = 100
    model.fit(X, Y, epochs=epochs, batch_size=128)
    # save model
    mp = r'./LSTM_Operation.h5'
    model.save(mp)
    
    # use LSTM model to predict
    for _ in range(100):
        start = np.random.randint(0, len(dataX)-1)
        # print(dataX[start])
        number1 = dataX[start][0:BINARY_DIM]
        number2 = dataX[start][BINARY_DIM:]
        print('='*30)
        print('%s: %s'%(number1, binary2int(number1)))
        print('%s: %s'%(number2, binary2int(number2)))
        sample = np.reshape(X[start], (1, 2*BINARY_DIM, 1))
        predict = np.round(model.predict(sample), 0).astype(np.int32)[0]
        print('%s: %s'%(predict, binary2int(predict)))

    转载于:https://www.cnblogs.com/jclian91/p/9867229.html

    展开全文
  • n加法——元素阶的终极规律

    千次阅读 2020-03-11 10:48:22
    Z6={0,1,2,3,4,5}, 6 加法的构成的群中,群的阶=?...取其中的元素1,不停地对自身进行6加法,即对本身进行幂运算。 可得: 5=5 5+5=10 5+5+5=15 5+5+5+5=20 5+5+5+5+5=25 5+5+5+5+5+5=30 故...

    Z6={0,1,2,3,4,5},模 6 加法的构成的群中,群的阶=?, 元素 5 的阶 |5 |=? 。

    我们知道,群的阶等于元素个数6,
    我们看<Z6,+>中的元素{0,1,2,3,4,5}。取其中的元素1,不停地对自身进行模6加法,即对本身进行幂运算。
    可得:
    5=5
    5+5=10
    5+5+5=15
    5+5+5+5=20
    5+5+5+5+5=25
    5+5+5+5+5+5=30
    故|5|=6
    考虑大数字不好计算,让我们通过编程找规律。

    /*
    模n加法,群的阶=n,元素的阶=最少几次方(几次相加)=本身。
    下面来求元素的阶
    */
    
    #include<iostream>
    #include<iomanip>
    using namespace std;
    int as(int a)
    {
    	int i, j = 0;
    	for (i = 2; i < a; i++)
    		if (a % i == 0)
    		{
    			j = 1; break;
    		}
    	return j;
    }
    int main()
    {
    	int x, y, i;
    	int a = 15, b = 4;//a为元素个数和模a加法中的a.b为预留空间
    	for (i = 0; i < a; i++)
    		cout << setw(b) << i;
    	for (y = 2; y <= a; y++)
    		//	if(as(y))
    	{
    		cout << endl << setw(b) << y;
    		for (x = 1; x < y; x++)
    			for (i = 2; i < y + 2; i++)
    				if ((i * x) % y == x)
    				{
    					cout << setw(b) << i-1; break;
    				}
    	}
    	return 0;
    }
    

    最上方
    运行结果最上方一行为元素,最左方一列为元素个数,其它均为元素的阶。
    不难看出:元素的阶=n/(n与元素的最大公约数)
    |5|=6/(6与5最大公约数=1)=6

    展开全文
  • 2运算百度百科

    2020-10-30 14:13:24
    与四则运算相同,2运算也包括2加法2减法、2乘法、2除法四种二进制运算。与四则运算不同的是2运算不考虑进位和借位,2算术是编码理论中多项式运算的基础。2算术在其他数字领域中的应用也是很广泛的...

    模2运算是一种二进制算法,CRC校验技术中的核心部分。与四则运算相同,模2运算也包括模2加法、模2减法、模2乘法、模2除法四种二进制运算。与四则运算不同的是模2运算不考虑进位和借位,模2算术是编码理论中多项式运算的基础。模2算术在其他数字领域中的应用也是很广泛的。

    中文名

    模2运算

    外文名

    mod 2

    所属学科

    数学

    释    义

    一种二进制算法

    应用领域

    数理科学

    包    含

    模2加法、模2减法、模2乘法、模2除法

    目录

    1. 模二运算
    2. 模二加法
    3. 模二减法
    4. 模二乘法
    5. 模二除法

    模二运算

    编辑

    移位寄存器的每一级只可能有两种不同的存数(或状态),分别用0和1来表示。这里, 0和1不再具有一般数量的含义,而只具有逻辑含义。对于这样一种只包含0和1两个元素(符号)的集合(叫做二元集)来说,普通的四则运算不再适用,因而必须重新规定一种新的运算规则。所谓模2运算就是这样一种新的运算规则。 [1] 

    模2运算是一种二进制算法,CRC校验技术中的核心部分。与四则运算相同,模2运算也包括模2加、模2减、模2乘、模2除四种二进制运算。而且,模2运算也使用与四则运算相同的运算符,即“+”表示模2加,“-”表示模2减,“×”或“·”表示模2乘,“÷”或“/”表示模2除。与四则运算不同的是模2运算不考虑进位和借位,即模2加法是不带进位的二进制加法运算,模2减法是不带借位的二进制减法运算。这样,两个二进制位相运算时,这两个位的值就能确定运算结果,不受前一次运算的影响,也不对下一次造成影响。

    模二加法

    编辑

    所谓“模2加法”就是0和1之间的加法,其中0+0 =0,1+0 =0+1 =1,1+1=0(!)。这种运算在通信和计算机上是常用的,而且并不神秘.你可以把0和1分别想成是“偶数”和“奇数”,那么前两个式子分别代表:偶数加偶数等于偶数,奇数加偶数等于奇数,而式1+1=0就是奇数加奇数等于偶数.对于任意多个数a1,a2,…,am(每个都是0或1),可以把它们做模2加法a1+a2+…+am。不难看出,当这m个数中有奇数个1时,结果为1,否则结果为0。

    对二进制数定义模2加法,规则非常简单:即每个数位上分别作模2加法,由此得出一个新的二进制数,例如[ 1101]+[111]+[101]=[1111],写成算式为

    个位数字共有3个1,所以模2加为1(不进位)。同样的,其他数位上也均有奇数个1,不同数位之间彼此无关地运算,所以模2加法是不进位的加法。 [2] 

    模二减法

    编辑

    模2减法是一种不考虑借位的减法,其定义如下:

    0-0=0

    1-1=0

    1-0=1

    0-1=1

    同样,第四式代表了模2减法的特征,从它也可得出2=0及+1=-1的结论。在多位模减法中,每位都按上述定义进行运算,不考虑借位问题。例如:

    此结果和前面模2加法的结果完全一样,进而发现关于模2运算的一个重要特点,模2加法和模2减法实际上是一回事,所有用模2减法的地方都可用模2加法来代替,故不用给模2减法定义专用的符号。

    模2加的定义可以得出一个重要结论:奇数个1相加得1,偶数个1相加得0。这个结论在奇偶校验中是很有用的。 [3] 

    模二乘法

    编辑

    一位数的模2乘法定义如下:

    0×0=0

    0×1=0

    1×0=0

    1×1=1

    因为上述4条一位数的模2乘法定义在除法中也适用,所以模2除法是模2乘法的逆运算,并且用下面的乘法算式,互逆验算验证成功(自己备注)

    多位数的模2乘法与普通乘法一样演算,如:

    唯一的区别是,部分积相加时按模2加,即奇数个1相加得1,偶数个1相加得0。

    模二除法

    编辑

    模2除法是模2乘法的逆运算。如:

    上例结果是对的,只是中间省略了一步,商为0的那步骤(自己备注)

    模2除法具有下列三个性质:(没有讲到为什么要去除首位(自己备注)猜测和寄存器移位有关系,也有点类似算数除法竖式中每一步的商和除数的积和上面的被除数差的最高位是0例如163除以7

    1、当最后余数的位数小于除数位数时,除法停止。

    2、当被除数的位数小于除数位数时,则商数为0,被除数就是余数。(这条不是说所得余数去除首位(即左移一位),而是过程中余数做被除数,首位是0,所以被除数的位数小于除数位数,则商0,自己备注)

    3、只要被除数或部分余数的位数与除数一样多,且最高位为1,不管其他位是什么数,皆可商1。

    模2算术是编码理论中多项式运算的基础。模2算术在其他数字领域中的应用也是很广泛的。

    展开全文
  • 之前的模板因为用了string类,以及运算的时候常数太大,导致速度太慢,虽然比较方便但不算很通用,所以存一波kuangbin大大的模板 /* * 高精度,支持乘法和加法 */ struct BigInt { const static int mod = ...
  • 计算机组成原理之2运算

    千次阅读 2020-05-07 09:27:13
    2运算是一种二进制运算,与普通的四则运算相同,2运算也包括2加法2减法、2乘法、2除法。但是与普通四则运算不同的是,2运算不考虑进位和借位,两个二进制位相运算的时候,这两个值就能确定出结果,...
  • 6加法群(Z6,+)认识循环群及其特点

    万次阅读 多人点赞 2018-09-23 17:57:18
    刚开始接触循环群不容易理解,不妨以6加法群&lt;Z6,+&gt;入手,来认识循环群的特点。...取其中的元素1,不停地对自身进行6加法,即对本身进行幂运算。 可得: 1^1=1 1^2=1+1=2 1^3=1+1+1=3 1^4=1+...
  • 离散 模运算

    千次阅读 2019-08-31 20:05:58
    n加法 两数进行普通加法后,对和进行取余,n乘法 两数进行普通乘法后,对积进行取余,, ▫ > ▫是n加法 G={0,1,2,3,4,...,n-1} 模加法有幺元:0,并且每个元素都有逆元;, * > *是n乘法 G={1,2,3,4,...,n-1}...
  • 转载于:... 在这里,我们约定,能用int表示的数据视为单精度,否则为高精度。所有函数的设计均采用带返回值的形式。 本文包含 1.高精度加法 2.高精度减法 ...4.高精度除法...
  • CRC校验码的运算

    2019-12-05 15:47:57
    运算中,加法和减法都是做异或运算。具有r个校验位的多项式能检测出所有长度小于等于r的差错。 设有原始帧 11 0101 1011,生成多项式为G(x)=$x^4$+x+1,求实际传输帧为多少。 思路:生成多项式G(x)=10011 原始帧...
  • 数论-模运算与同余的性质 模运算 基础 取模运算:a % p(a mod p),表示a除以p的余数。 运算 1.p加法:(a + b) % p = (a%p + b%p) % p 2.p减法:(a - b) % p = (a%p - b%p)...4.幂p :(a^b) % p = ((a % p)^b...
  • 在django中的模板下我们知道变量使用{{xxx}}来呈现,可是当出现两个...#与加法的性质一样,只不过是把第二个参数变成负数进行运算,返回的结果是value-value2 #假如value=4,value2=8,则返回的结果是-4 #乘法 {% width
  • 目录1 概述2 加法运算3 减法运算4 乘法运算5 C++实现 1 概述   由m×nm \times nm×n个数aija_{ij}aij​排成的mmm行nnn列的数表称为mmm行nnn列的矩阵,简称m×nm \times nm×n矩阵。记作: A=[a11a12⋯a1na21a22⋯...
  • 溢出(正溢出、负溢出) 溢出检测(变形补码、模4补码) 加法器的实现(1位全加器) 串行进位加法器 并行进位(先行进位)加法
  • 加法运算: 复数的加法按照以下规定的法则进行:设z1=a+bi,z2=c+di是任意两个复数,则它们的和是(a+bi)+(c+di)=(a+c)+(b+d)i; 例如:a = 1+2i,b = 3+4i 即可得 a+b = 4+6i 减法法则: 复数的减法按照以下规定的法则...
  • 232加2^{32}加232加,计为+++:意思是普通加法的结果再进行232加2^{32}加232加计算。 如24加2^424加. 若,a = 14,b=15,(+)表示24加2^424加 则,a(+)b=(a+b)  mod  24=(14+15)mod16=...
  • C/C++高精度四则运算模板

    千次阅读 2019-03-19 19:57:00
    1.高精度加高精度(加法) 模拟小学算式 1 4 7 + 6 5 2 1 2 现在模拟这个算式即可从低位到高位每一位相加 7 + 5 = 12 这一位应该为2, 而进位则为12 / 10 = 1 4 + 6 + 1 = 11 这一位为1,而进位则为11 / 10 = 1; 1 ...
  • 用 Verilog HDL 来描述加法器是相当容易的,只需要把运算表达式写出就可以了,见下例。 module add_4( X, Y, sum, C); input [3 : 0] X, Y; output [3: 0] sum; output C; assign {C, Sum } = X + Y; endmodule...
  • 窥探SQL: 4.集合运算

    2020-12-22 12:43:23
    表的加减法1.1集合运算1.2 表的加法-UNIONUNION 与 OR 谓词包含重复行的集合运算UNION ALLbag模型 和 set模型2.连结(JOIN) 1.表的加减法 1.1集合运算 集合,在数据库领域表示记录的集合. 具体来说,表、视图和查询的...
  • 比较简短的高精度加法和减法运算模板。大除法的日后更新。 1 /* 两个非负的大整数相加 */ 2 void big_plus(char a[],char b[],char ans[]) 3 { 4 int c[N],d[N]; 5 memset(c,0,sizeof(c)); memset(d,0,...
  • 数字图像处理4:图像的像素级运算

    千次阅读 2018-12-04 21:40:09
    图像处理入门:图像的像素级运算 ...加法运算: OpenCV中的加法是一种饱和算法,而python中的numpy是一种操作。   import cv2 import numpy as np     if __name__=='__main_...
  •  使用cv2.add()将两幅图像进行加法运算,也可以用numpy运算,直接img+img1。两幅图像的大小和类型必须一致,或者第二个图像可以是一个简单的标量值。  两种操作的本质区别在于OpenCV的加法是一种饱和操作,加到顶...
  • C语言-四则运算.docx

    2020-11-15 09:03:01
    功能结构图 四则运算 加法运算 减法运算 乘法运算 除法运算 求运算 混合运算 理 f 统计正确率 2?程序功能 进行整数的加减乘除和求运算程序采用随机产生 1~100的两个数进行运算每种运算有 10个题目用户输入对应的...
  • 1.1 表的加法-UNION 1.1.1 UNION 1.1.2 UNION ALL 1.1.3 bag模型和set模型 1.1.4 隐式类型转换 1.2 MySQL不支持交运算INTERSECT 1.3 差集,补集与表的减法 1.4 对称差 1.5 助并集和差集实现交集运算 二、...
  • 算术运算符(7个):+ - * / % ++ --,它们分别为:加法、减法、乘法、除法、求(也叫求余)、自增、自减。这里注意一点:在Golang中只支持后置++、后置–。 比较运算符(6个):== != > < >= <=,它们分别...
  • 先说一下题目,要求必须用python完成,看了老师的代码,嗯……,还是自己写吧 ...#多项式加法 def add(a,b): a = list(map(int, a)) b = list(map(int, b)) c=[0,0,0,0,0,0,0,0] for i in range(...
  • Python运算

    2021-02-21 22:58:46
    (5)取模运算符:用“%”表示,符号前的变量以符号后的变量为进行取模运算。取模运算是求两个数相除的余数 (6)求幂运算符:使用符号“**”表示,符号前的变量以符号后的变量为幂进行求幂运算。 (7)取整...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 250
精华内容 100
关键字:

模4加法运算