分类 数学基础 下的文章

3n + 1 问题——引发的缓存思考


问题描述

有这样一个规律:对任意大于 1 的自然数 n,如果 n 为奇数,将其变化为 3n + 1;如果 n 为偶数,将其变化为 n/2。经过若干次变化后,一定会使 n 变为 1。

如果 n = 5:

  • 5 -> 16 -> 8 -> 4 -> 2 -> 1

如果 n = 3:

  • 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

现在,输入一个整数 n,请计算出总的变化次数。例:n = 5,l = 5;n = 3,l = 7。(l 表示变化次数)


对角线问题


问题

这里有 n * n 矩阵,要求左上到右下的对角线上都为 x,其他地方为 y。x、y 任意值,但不相等。

x y y ... y
y x y ... y
y y x ... y
. . . ... .
. . . ... .
y y y ... x


二分查找


二分查找是一个比较简单的算法,用 C++ 语言实现如下:

template <typename T>
int binary_search(
        const T& key,  // 搜索元素 key
        vector<int>::const_iterator data,  // 数组起始位置
        int N)  // 元素个数
{
    // 左闭右闭
    int low = 0;
    int high = N - 1;

    while (low <= high) {

        int mid = low + (high - low) / 2;

        if (key < *(data + mid))
            high = mid - 1;
        else if (key > *(data + mid))
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

用法:
// vector<int> arr = {1, 2, 3, 4, 5, 65};
// cout << binary_search(5, arr.cbegin(), 6) << endl;
// cout << binary_search(1, arr.cbegin(), 6) << endl;
// cout << binary_search(4, arr.cbegin(), 6) << endl;


动态规划-用编辑距离解释


前言

什么是编辑距离呢?

我们把“从字符串A到字符串B”的最少操作次数称作编辑距离。操作包含了:插入,删除,替换。比如字符串A = “abc”,字符串B = “abcd”,那么从A到B只需要增加一个字母“d”,所以编辑距离为1;同样的,从B到A只需要删除“d”,所以编辑距离也为1。

状态转移

将需要求解的问题,转移成子问题的过程,叫做状态转移。刻画状态转移的表达式称为状态转移方程式


排列与组合


前言

诚然,排列组合作为高考数学里的送分题,它的出现让我这样的弱鸡一度欢喜。地处中央,上承“选择填空”,下启“数列圆锥”,紧绷的神经在这里可以微微松懈。

我依然记得排列公式是,而组合是

那么对于计算机来说,要怎样才实现排列组合呢?Python告诉你。