分类 数学基础 下的文章

对角线问题


问题

这里有 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告诉你。


浅谈递归思想


前言

如果一谈到“递归”你的脑海就浮现出“自己调用自己”,我想说:“你可能并不懂递归”。当然了,这仅仅是个人鄙见。许多时候,递归确实在“自己调用自己”。我们知道这个道理吧,想用递归解决实际问题却又犯难了——怎么就写不出代码来了呢?

我想异于网上千篇一律文章的讲法,小小的别开生面一回,用自己认为容易理解的方式来阐述递归思想。当然啦,如同标题所说,只能浅谈而已。因为,我并不认为自己已经很懂。