在线编程(刷题)的低级错误

最近几天在一些OJ网站上刷了不少算法题,都是直接在网页上写代码,脑中调试,然后提交,发现提交通不过大概有以下几种情况:

  1. 算法设计出现根本性错误,一般是对题意有误解,或重要的分支情况未考虑到;
  2. 算法设计基本正确,但是有一些边界情况未考虑到;
  3. 时间复杂度太高;
  4. 低级错误。

以上的1、2、3属于算法的基本功,无论你是在线刷题,还是用IDE刷题,都避免不了,但是对于低级错误,IDE的编辑器静态分析就能发现一批,编译时又能发现一批,似乎也不是什么问题。

问题在于,技能的反面就是解决问题,解决一些低级错误是会浪费时间的,而且,有一些低级错误会躲过编译器,造成更大的危害,因此很有必要尽量减少这些低级错误。在线刷题时,我自己常见的低级错误(主要是java语言的):

  1. 没有写分号,或者写了中文分号;
  2. 括号未匹配;
  3. 未记住一些API的名称,比如HashMap中的containsKey而不是contains;
  4. 拼写错误,导致API调用错误,甚至标识符前后不一致;
  5. 更改了某个标识符,但是没有更改完全;
  6. 忘记写返回语句,或者某些支路忘记写返回语句,甚至返回了错误的变量或变量类型;
  7. 重复声明变量,比如循环内外各申明一次;
  8. 想要在循环外使用循环变量,但没有在外面声明;

暂时这些,以后不断补充。

如何改善?我发现我这么多年来都犯了一个错误,因为自己粗心,又觉得不可能不犯错误,就放弃了改善的机会,有些放任自流,从认识上就需要提高。以下是一些观点和方法,希望慢慢能标本兼治:

  1. 人都会犯错误,甚至犯低级错误,即所谓的粗心,粗心不能根除,但是可以改善;
  2. 意识到自己的低级错误并改善,而不要视而不见,放任自流;
  3. 适当放慢速度,萝卜快了不洗泥;
  4. 第一遍写的时候随时自我复查,要习惯脑子里有一个角色在复查,争取一次写对;
  5. 写完复查一遍。
  6. 及时总结自己犯了哪些低级错误。

这里谈的都是低级错误,还每涉及到如果提高程序的正确性,这一点以后再总结。

逆序对计数问题

有一组数,对于其中任意两个数组,若前面一个大于后面一个数字,则这两个数字组成一个逆序对。计算给定数组中的逆序对个数。

《建军大业》:创业的细节

建军大业

跑到电影院去看这部一般来说应该免费接受教育的电影,一是满足某人的恶趣味去数星星,二是自己也对一切创业史感兴趣。主旋律的题材,香港导演,一堆小鲜肉演员,作为电影来说还是及格的,只是这个故事我们已经看过无数遍了。反倒是一些细节我比较感兴趣,而还有一些细节却在电影中看不出来,看来真感兴趣还是得去读史料。

  1. 电影中有一段南昌起义后征用南昌银行中金条的小场景,甚至还有拿枪顶着人头同时又打欠条的镜头,一般历史的角度都是从政治军事来看的,但是我对经济的角度却最感兴趣,想知道民国时期,军阀割据时,各家是如何解决军饷问题的。
  2. 南昌起义基本失败后,朱德手下只剩下八百人,但是到了井冈山会师时,又拉出了几万人的队伍,包括打散了的叶挺、贺龙等等,后来都扩充了军队,我其实对这些人在阶段性失败后如何东山再起比较感兴趣,一般的文艺作品貌似着墨不多,可能一般对毛泽东的路线斗争与邓小平的几起几落写得多一些。
  3. 这次电影的战斗效果很爆表,我都很怀疑真正的历史火力有没有那么猛。然后,电影中还有毛泽东买军火的片段,我对当年的军火的来源与流动也很感兴趣。电影中还提到了汉阳兵工厂,它的百年历史,拍成电影或电视剧应该也很有意思。

硬币组合问题

假设我们有面值为1,2,5,10,25的硬币,那么组成面值共有多少种可能的情况?这是美分的情况。

一般的假设我们有面值为的硬币,其中,那么组成面值共有多少种可能的情况?

按照一般找钱的顺序,我们从大钱开始考虑,这样剩下的面值才能比较迅速的减小。

1.递推式1

考虑美分的情况,假设我们要组成面值101,记组合数为f(101),如果使用了一个25分的,那么剩下的情况数应该是f(76),但是注意,这个f(76)已经不能使用25分的硬币了,简单起见,我们把硬币种类编号引入组合数,当可以用编号1~k时,组合数记为f(m,k),所以上面的分析可以记为组合数f(101,5),使用了一个25分时,剩下的情况数为f(76, 4),针对25美分的使用,可以得到下表

25分个数 剩余
0 f(101, 4)
1 f(76, 4)
2 f(51, 4)
3 f(26, 4)
4 f(1, 4)

将第二列的数字相加,就得到了结果。现在要求的问题简化了,只需要考虑面值为1,2,5,10的情况,同样的以f(76, 4)为例,可以化简为f(76,3),f(66,3)…f(6,3),这样递归迭代下去,我们最终要解决的子问题是f(m,1),用一种面值来组成m,显然,只需要面值m能被整除即可,由此结束了递归迭代。

按照这种思路,直接写成Java代码如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        return countCoins(n, coins.length - 1, coins);
    }

    public int countCoins(int n, int level, int[] coins) {
        if(level == 0) {
            return n % coins[0] == 0 ? 1 : 0;
        }
        int ways = 0;
        for(int i = 0; i*coins[level] <= n; i++) {
            ways += countCoins(n-i*coins[level], level-1, coins);
        }
        return ways;
    }

2. 递推式1的动态规划

在1中,我们通过不断的减去大的硬币面值,求解各个子问题,得到最终的结果,不难发现,这些子问题存在很多重复,比如考虑如下的计算路径:f(101, 5)->f(76, 4)->f(16,3)…和f(101, 5)->f(26, 4)->f(16,3)…后面的计算时完全重合的,因此,如果把这些计算结果缓存起来,可以大大提高计算的速度,这就是动态规划的思想。我们需要建立如下的一张表,以下考虑计算f(6,5)

  0 1 2 3 4 5 6
1 1 1 1 1 1 1 1
2 1 1 2 2 3 3 4
5 1 1 2 2 3 4 5
10 1 1 2 2 3 4 5
25 1 1 2 2 3 4 5

注意到我们的递推式,每次分解出很多项,那么在动态规划填表时,也就需要很多项目相加才行。动态规划时,先填满第一行,再根据递推式计算第二行,直到计算最后一行。

由此得到Java代码如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[][] ways = new int[coins.length][n + 1];
        for(int j = 0; j <= n; j++) {
            ways[0][j] = j % coins[0] == 0 ? 1 : 0;
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = 0; j <= n; j++) {
                if(j < coins[i]) {
                    ways[i][j] = ways[i-1][j];
                }
                else {
                    for(int k = 0; k*coins[i] <= j; k++) {
                        ways[i][j] +=  ways[i-1][j-k*coins[i]];
                    }
                }
            }
        }
        return ways[coins.length - 1][n];
    }

注意到最后一行其实只需要计算最后一个元素。(因为它只跟前一行相关),所以上述代码还可以修改节约时间,不过代码会变得不太美观,这里就不写了。

3 递推式2及其动态规划

我们发现,递推式1中,一项被分解成多项,导致计算过程中做了相当多的加法,能不能简化一下呢?

还是考虑f(101,5),我们可以这样考虑,首先不使用25美分,情况数为f(101,4),其次是使用25美分的情况,那么至少要使用一个25美分,如果去掉这个25美分,则相当于剩下的76美分,既可以使用25美分,也可以不用,实际上就是f(76,5),由此得到递推关系,这样在动态规划填表时,每次取上一行的数与本行之前相距的数相加。注意当

由此得到动态规划的代码如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[][] ways = new int[coins.length][n + 1];
        for(int j = 0; j <= n; j++) {
            ways[0][j] = j % coins[0] == 0 ? 1 : 0;
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = 0; j <= n; j++) {
                if(j < coins[i]) {
                    ways[i][j] = ways[i-1][j];
                }
                else {
                    ways[i][j] = ways[i-1][j] + ways[i][j-coins[i]];
                }
            }
        }
        return ways[coins.length - 1][n];
    }

4 递推式2的简化

仔细考察我们填表的过程,填第二行时,左边的较小元素和第一行一样,右边较大的元素在第一行的基础上加上本行较小的一个元素,所以其实只需要存储一行元素就行了,计算 时, 在左边已经计算出来了,而直接使用自身存储便可。由此得到更加简化的动态规划代码:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[] ways = new int[n + 1];
        for(int j = 0; j <= n; j++) {
            ways[j] = j % coins[0] == 0 ? 1 : 0;
        }
        for(int i = 1; i < coins.length; i++) {
            for(int j = coins[i]; j <= n; j++) {
                ways[j] += ways[j-coins[i]];
            }
        }
        return ways[n];
    }

考虑第一行,如果设置ways[0] = 1,j<coins[0]时,ways[j] = 0,那么第一行同样可以用递推式ways[j] += ways[j-coins[i]]得到。代码可进一步简化如下:

    public int countCoins(int n, int[] coins) {
        if(n < 0) return 0;
        int[] ways = new int[n+1];
        ways[0] = 1;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= n; j++) {
                ways[j] = ways[j] + ways[j-coins[i]];
            }
        }
        return ways[n];
    }

全排列生成算法实现

我们知道n个相异元素的全排列种数为n!,那么由程序如何生成n个相异元素的排列呢,对此问题的研究很多,本文首先用Java实现了《算法设计与分析基础》一书中4.3节的三个算法。

1 插入法

这种算法最直观,基于排列的递推定义。符合所谓减治法的思想,或者说是数学归纳法的思想,如果n-1个元素已经排好,我们只需要把第n个元素插入这些排列中所有可能的位置即可,每个元素有n个位置可以插入,刚好是(n-1)!*n=n!种情况。如果插入的时候,方向先从右到左,再从左到右循环,那么每两个相邻的排列将只有最小的差异,即只有某两个相邻元素相异。比如已经有12,21则12从右到左插入3,21从左到右插入3,最终得到123,123,312,321,231,213。具体的Java代码如下,这是一个递归算法。

public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if(n <= 0) return permutations;
        if(n == 1) {
            permutations.add( new int[]{1});
            return permutations;
        }
        ArrayList<int[]> remainders = getPermutations(n-1);
        for(int i = 0; i < remainders.size(); i++) {
            int[] remainder = remainders.get(i);
            for(int j = 0; j < n; j++) {
                int[] permutation = new int[n];
                if(i % 2 ==0) {//insert from right to left
                    System.arraycopy(remainder, 0, permutation, 0, n - 1- j);
                    permutation[n - 1 - j] = n;
                    System.arraycopy(remainder, n - 1 - j, permutation, n - j, j);
                }
                else {//inset from left to right
                    System.arraycopy(remainder, 0, permutation, 0, j);
                    permutation[j] = n;
                    System.arraycopy(remainder, j, permutation, j + 1, n - 1- j);
                }
                permutations.add(permutation);
            }
        }
        return permutations;
	}

2 JohnsonTrott算法

在Johnson-Trotter算法中,每次循环都进行一次满足条件的相邻元素的交换,直到不存在满足条件的可交换的元素,此时说明所有排列的情况均已输出,算法结束。

具体过程如下:

  1. 初始化所有元素的移动方向为左,输出序列本身
  2. 移动最大的可移动的元素(当元素移动方向上的元素比自己小时,才能移动)
  3. 反转所有比移动元素大的所有元素的移动方向
  4. 重复2~3步,直到不能移动为止

具体例子

上面的算法流程有些抽象,现在举个例子来加深理解。假设现在要计算所有排列。首先是将所有元素的移动方向为标记为向左,我们可以表示成这样,然后根据算法流程中的步骤2,移动最大的可移动元素。这里的可移动元素是指在其移动方向上的相邻元素比自己小时,例如都是可移动元素,因为在他们的移动方向上(左移)的相邻元素:1,2分别比2,3小,而每次都只移动这些可移动元素中最大的那个项。接着,在每次交换完成之后,寻找所有比当前交换元素大的元素,将他们的移动方向反转一下。

下面列出在计算过程中所有的情况

Java代码如下:

public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        int[] first = new int[n];
        boolean[] mobile = new boolean[n];
        for(int i = 0; i < n; i++) {
            first[i] = i + 1;
            mobile[i] = true;//true:left; false:right;
        }
        permutations.add(first);

        while(true) {
            int[] last = permutations.get(permutations.size()-1).clone();
            int k = findLargestMobile(last, mobile);
            if(k == -1) break;
            int max = last[k];
            int neighbor = mobile[k] ? k - 1 : k + 1;
            swap(last, k, neighbor);
            swap(mobile, k, neighbor);
            reverseLarger(last, mobile, max);
            permutations.add(last);
        }
        return permutations;
    }

    private static int findLargestMobile(int[] array, boolean[] mobile) {
        int k = -1;// -1 means can't find mobile element
        int max = -1;
        for(int i = 0; i < array.length; i++) {
            int j = mobile[i] ? i - 1: i + 1;
            if(j < 0 || j >= array.length) continue;
            if(array[i] > array[j] && array[i] > max) {
                max = array[i];
                k = i;
            }
        }
        return k;
    }

    private static void reverseLarger(int[] array, boolean[] mobile, int max) {
        for(int i = 0; i < array.length; i++) {
            if(array[i] > max) mobile[i] = !mobile[i];
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private static void swap(boolean[] array, int i, int j) {
        boolean temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

3 字典序生成法

字典序生成法在当前已经生成的排列上寻找下一个字典序的排列:

  1. 找到最长的递减序列后缀,记这个序列的前一个元素为i,如果找不到i,则证明已经生成了最后一个完全倒序的排列,生成完毕。
  2. 在前述后缀中,找到比元素i大的最小元素j,并交换i和j;
  3. 将后缀逆序排列。
  4. 重复1到3。

比如排列123654,首先找到后缀654,在找到中间最小大于3的4,交换得到124653,然后将后缀逆序得到124356,又如排列123645,找到后缀5,交换得到123654,后缀只有一个,逆序后不变仍未123654。

具体的Java代码如下:

public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if(n <= 0) return permutations;
        int[] first = new int[n];
        for(int i = 0; i < n; i++) first[i] = i + 1;
        permutations.add(first);

        while(true) {
            int[] last = permutations.get(permutations.size()-1).clone();
            int i = n - 1;
            while(i > 0) {
                if(last[i] > last[i-1]) {
                    break;
                }
                i--;
            }
            if(i==0) break;

            int j = n - 1;
            while(j >= i) {
                if(last[j]>last[i-1]) {
                    break;
                }
                j--;
            }
            swap(last, i-1, j);

            int k = n - 1;
            while(i < k) {
                swap(last, i, k);
                i++;
                k--;
            }
            permutations.add(last);
        }
        return permutations;
    }

4 序数法

这个方法把n!个排列与0~n!-1之间的数一一对应起来,这样,我们就可以按照0~n!-1的次序,逐一生成相关的排列。这个对应的关键在于0~n!-1之间的数m,可以用如下的方式表示: ,其中

故m对应序列,现在再把这个序列和排列一一对应起来,n-1位的序列对应n位的排列。

表示排列p中的数i+1所在位置的右边比它小的数的个数。比如对于排列p=4213,4,3,2的逆序数分别为3,0,1,由此对应为,反过来呢,如果知道了逆序数,也可以一一恢复出排列来。比4小的有3个,4只能放最左边,比3小的为0个,3只能放最右边,比2小的一个,2放第二个位置,剩下的放1,故为4213。

0 000 1234 12 200 1423
1 001 2134 13 201 2413
2 010 1324 14 210 1432
3 011 2314 15 211 2431
4 020 3124 16 220 3412
5 021 3214 17 221 3421
6 100 1243 18 300 4123
7 101 2143 19 301 4213
8 110 1342 20 310 4132
9 111 2341 21 311 4231
10 120 3142 22 320 4312
11 121 3241 23 321 4321

Java代码如下:

    public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        int[] factorials = new int[n+1];
        factorials[0] = 1;
        for(int i = 1; i <=n; i++) {
            factorials[i] = i * factorials[i - 1];
        }// init factorial array
        for(int m = 0; m < factorials[n]; m++) {
            int remainder = m;
            int[] permutation = new int[n];
            for(int i = n-1; i >=0; i--) {
                int count = remainder / factorials[i];
                remainder = remainder % factorials[i];
                setPosition(permutation, count, i + 1);
            }
            permutations.add(permutation);
        }
        return permutations;
    }

    private static void setPosition(int[] permutation, int count, int num) {
        int zeros = 0;
        for(int i = permutation.length - 1; i >=0; i--) {
            if(permutation[i] == 0) zeros++;
            if(zeros == count + 1) {
                permutation[i] = num;
                break;
            }
        }
    }

5 轮转法

基准序列,先逐步生成以开头的所有排列:

  1. 先生成以开头的所有排列
  2. 再生成以打头的排列,除了前述2个排列外,再将其后三位从左至右轮转2次,得到4个新排列,一共6个排列;
  3. 再生成以打头的排列,除了前述6个排列外,再将其后四位从左至右轮转3次,得到18个新排列,一共24个排列;
  4. 依次类推,一直到生成以开头的所有排列为止。

然后将基准序列从左到右轮转一次,生成以开头的所有排列,依次类推,直到生成以开头的所有排列。

java代码如下:

    public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        int[] first = new int[n];
        for(int i = 0; i < n; i++) {
            first[i] = i + 1;
        }
        for (int i = 0; i < n; i++) {
            if(i > 0) {
                rotateLeft(first, 0, n);
            }
            int[] base = first.clone();
            permutations.addAll(rotateBase(base));
        }
        return permutations;
    }

    private static ArrayList<int[]> rotateBase(int[] base) {
        ArrayList<int[]> permutations = new ArrayList<int[]>();
        permutations.add(base);
        for(int prefixSize = base.length - 2; prefixSize >= 1; prefixSize--) {
            int currentSize = permutations.size();
            for(int i = 0; i < currentSize; i++) {
                int[] last = permutations.get(i);
                for(int j = 0; j < base.length - prefixSize - 1; j++) {
                    int[] rotated = last.clone();
                    rotateLeft(rotated, prefixSize, base.length);
                    permutations.add(rotated);
                    last = rotated;
                }
            }
        }
        return permutations;
    }

    private static void rotateLeft(int[] permutation, int start, int end) { 
      // rotate from left to right
        int temp = permutation[start];
        for(int i = start; i < end - 1; i++) {
            permutation[i] = permutation[i + 1];
        }
        permutation[end-1] = temp;
    }

6 回溯法

我们将问题形象化,假如你手里有编号为1、2、3的3张扑克牌和编号为1、2、3的三个盒子。现在需要将这3张扑克牌分别放入3个盒子里,并且每个盒子有且只有一张扑克牌。总共有几种放法呢?

首先你来到了1号盒子面前,你现在手里有3张扑克牌,先放哪一张好呢?很显然三者都要尝试,那就姑且约定一个顺序:每次到一个盒子面前,都先放1号,再放2号,最后放3号。于是你在一号盒子里放入了编号为1的扑克牌。来到2号盒子面前,由于之前的1号扑克牌已经不在手中,按照之前约定的顺序,你将2号牌放到了2号盒子里。3号也是同样。你又往后走当你来到第4个盒子面前,诶,没有第四个盒子,其实我们不需要第4个盒子,因为手中的扑克牌已经放完了。

你发现了吗?当你走到第四个盒子前的时候,已经完成了一种排列,即“1 2 3”。然而并没有到此结束,产生了一种排列之后,你需要立即返回。现在你已经退到了3号盒子面前,你需要取回之前放在3号盒子中的扑克牌,再去尝试看看还能否放别的扑克牌,从而产生一个新的排列。于是你取回了3号牌,但由于你手中只有3号牌,你只能再次退回到2号盒子面前。

你回到2号盒子后,收回了2号牌。现在你的手中有2张牌了,分别是2号和3号牌。按照之前的约定,现在需要往2号盒子中放3号扑克牌(上次放的是2号牌)。放好后,你来到3号盒子面前,将手中仅剩的2号牌放入了3号盒子。又来到了4号盒子面前,当然没有4号盒子。此时又产生了一个新的排列“1 3 2”。

接下来按照刚才的步骤去模拟,便会依次生成所有排列:“2 1 3”、“2 3 1”、“3 1 2”和“3 2 1”。

Java代码实现如下:

    public static ArrayList<int[]> getPermutations(int n) {
        ArrayList<int[]> permutations = new ArrayList<>();
        if (n <= 0) return permutations;
        boolean[] visited = new boolean[n];
        int[] current = new int[n];
        dfs(permutations, current, visited, 0);
        return permutations;
    }

    private static void dfs(ArrayList<int[]> permutations, int[] current, boolean[] visited, int step) {
        int n = current.length;
        if(step == n) {
            permutations.add(current.clone());
            return;
        }
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                current[step] = i + 1;
                visited[i] = true;
                dfs(permutations, current, visited, step + 1);
                visited[i] = false;
            }
        }
    }

当然,如果改用栈,也可以变成非递归的版本。

后记

对一个问题用不同的算法解决,可以综合复习各种算法思路。

另外重要的一点就是,如果看过一个算法没有写代码实现过,很可能会有一些没有真正理解的细节存在。

如果以后再发现好的算法,还会再补充。

我的PC软件列表

我一直比较喜欢试用各种软件,也喜欢看别人分享的软件推荐的文章,总的来说,我是一个工具控。现在工作告一段落,也想借这闲暇时间把自己目前正在使用的软件总结一下,一是备忘,二是分享,三是留待一两年后再看,什么变了,什么没变。

我目前电脑主要使用的操作系统是Windows 10,但是我倾向于使用一些可以跨平台使用的软件,这样万一我想换平台则成本比较低。下面主要列举的是软件,可能会适当涉及在线服务。

1 操作系统

  • Windows 10 :所有的笔记本、台式机、Surface都使用Windows 10了,一是安全起见,二来我也觉得Windows 10还是比较好用的。开启了Bash On Ubuntu On Windows子系统后,也不用装其他的命令行工具,甚至Linux系统也用得很少了。
  • Deepin Linux :现在已经过了喜欢折腾系统的阶段,觉得操作系统最好开箱即用,而深度在这一点上做到了极致,预装了很多国人必备的软件比如WPS、QQ等。虽然在主力笔记本上使用三硬盘双系统,但是其实现在用得也不多。

2 文本与写作

  • Office365 :其实还是很喜欢Office软件,之前在工作中用得不少,现在买了Office 365服务,其实也用得不多,可能用最多是Excel了。
  • Typora :非常好用的markdown编辑器,这篇博客就是这么写的。
  • Jekyll + Github Pages:这是现在的主力写作平台,在诸多静态博客生成器中选择了Jekyll,只是因为这是GitHub默认支持的,懒得折腾了。

3 浏览器

  • Chrome:主力浏览器。其中重要的插件包括AdBlock、Checker Plus for Gmail™、Proxy SwitchyOmega、Save to Pocket、惠惠购物助、印象笔记·剪藏等。
  • IE11:没办法,工行只能用IE。
  • Firefox:现在用得比较少了,出于感情因素一直装着。

4 通信软件

  • TIM:替代QQ,没有杂七杂八的东西。
  • 微信 for Windows 10:发现都是腾讯家的。
  • Telegram:刚刚接触,看重它的保密通信。

5 系统增强

  • BandZip:压缩软件,界面清爽,功能强大。
  • CCleaner:垃圾清理软件。
  • Geek Unіnstaller:一款小巧的软件卸载工具,卸载时会查找注册表与垃圾文件。
  • RightMenuMgr:右键管理工具,可以删除一些不需要的右键项目。
  • FastCopy:文件快速拷贝工具。
  • f.lux:屏幕色温自动调节工具。
  • Everything:非常强大的文件搜索工具。
  • Wox:快速启动工具。
  • WGestures :全局鼠标手势工具。

6 下载工具

  • 迅雷极速版:虽然迅雷越来越水,但是这款极速版至少还没什么广告,是个比较纯粹的下载工具。
  • 百度网盘:可能是我用的唯二的百度服务了,另外一个是百度糯米。
  • 人人影视Pro:下载人人影视的作品很方便。
  • Resilio Sync:偶尔下点小东西,基于bittorrent原理的网盘工具。

7 影音娱乐

  • 射手播放器:虽然很久不更新了,但基本上还是万能播放器,最好的是还能自动下载字幕。
  • 网易云音乐UWP:主要在网易云音乐听歌,顺便本地歌曲播放也一起搞定了。
  • 多多猫app:可以看漫画的插件式强大软件,不过我也很少看就是了。

8 开发工具

  • Visual Studio 2017:工作中主用Visual Studio,自己的个人电脑习惯装最新版的。宇宙第一IDE,名不虚传。配上JetBrain家的Reshaper插件,写C#简直是所向无敌。
  • Intelij IDEA:偶尔也写写Java代码,再装上插件,写Pyhton之类的也毫无压力。
  • Visual Studio Code:又是微软出品的强大文本编辑器,装上插件后当轻量级的IDE用,写写Python,改改网站代码之类的。
  • Anaconda:一套完整的Python配套软件环境,包括数据分析常用的各种利器,今年开始研究机器学习,这是一个利器。
  • Octave:Matlab的开源版,偶尔写写简单的Matlab代码,或者当计算器算算矩阵。
  • Xshell :远程连接VPS时很好用。
  • GitExtension:一整套Git的解决方案,包括Git的GUI界面,以及文件比较工具等。
  • AutoHotkey:自动化脚本工具。

9 安全软件

  • WIndows Defender:不爱装其他杀毒软件,基本上等于裸奔了。
  • VeraCrypt:加密软件。

10 阅读软件

  • Kindle:偶尔也在电脑上用一下。
  • calibre:现在所有的电子书都交给它来管理了。
  • LightReader:轻量级的epub阅读器。
  • 福昕阅读器领鲜版:Foxit Reader的国内版,有pdf编辑功能。
  • DrowBoard PDF:在Surface上看PDF是神器。

11 其他

  • 印象笔记高级账户:它的特点是在各种笔记软件中比较简约均衡,Office365中的OneNote我也用,但是感觉太重了。
  • 科学上网工具:v2ray、XX-Net、Shadowsocks、Lantern,需要多种手段互为备份。
  • ZeroNet:最近刚接触的新鲜玩意儿,基于类似比特币的原理构建的P2P内容网络。
  • paint.net:偶尔改个图,当PhotoShop用。
  • Zotero:收集论文资料用。
  • Oracle VM VirtualBox:虚拟机软件。
  • FileZilla:FTP软件。
  • GeoGebra:一款有趣的几何作图软件。
  • Bither:一款比特币官方推荐的国人开发的比特币钱包。
  • TeamViewer:给家人远程桌面解决问题时用。

暂时就这些,发现有遗漏的再补充。

复习与复盘

上小学的时候,我们就有单元复习、期中复习、期末复习等等各种复习,整个初等教育学的东西其实总量有限,反反复复学的就是那点东西,因为它要面向大多数学生的水平,而且要打牢基础。

复习其实是学习新的东西中最重要的方法论之一,人的大脑会不断的选择性遗忘很多东西,只有通过复习才能巩固,而且更重要的是,大多数的学习材料是不可能第一遍就完全理解的,比如说你的第一遍学习掌握了30%,那么通过一轮复习可能达到50%,再复习一遍可能达到了80%,而复习的时候,一般不需要花第一次那么多时间,这样看来,复习的性价比是很高的。我觉得有几个原因,第一在复习的间隙,大脑得到机会重建神经网络,而不是一直处在紧绷状态,第二复习的时候由于已经掌握了很多基础,能够减轻自己理解的负担,集中精力在重点和难点上。

我觉得还有一个很重要的类似复习的过程,是回顾自己的思维过程,或者绕口一点,叫思考自己的思考过程,想一想自己在做出决策的时候,获得了哪些知识和信息,有什么样的情绪在其中,当时有多大的把握,是否受到了什么人的影响。这样做的次数多了,就越来越知道做出一个决策需要调研什么知识,需要关注自己的哪些非理性的有害的情绪,怎样建立信心,如何参考他人的意见等等。就像下围棋的人要复盘一样,重要的决策都值得像下围棋一样复盘,这和复习新知识有着相似的道理,复盘的时候,我们往往已经知道了决策的结果,也从当时的情绪中抽离出来,从而获得了更加客观看待自己思维过程的上帝视角。

子曰:吾日三省吾身。我以前只想到道德上的需要,想到“反省”一词,觉得有些负面,而用复盘一词,我觉得更加中性,也更能激励我的热情。

房贷的计算

之前我讨论过分期付款的实际利率,发现比较坑。今天再来讨论一下房贷,房贷的计算有很多在线的计算器,输入贷款额度,利率,以及贷款年数,选择等额本息还是等额本金还款,就可以得到每月还款的数值,下面我来分析一下这里面的原理,并简单讨论一下两种还款方式的优劣,以及提前还款是否有必要。

1.一个例子

假设贷款100万,年利率5%,贷款20年,使用前述计算器计算,得到等额本息还款每月6,599.56元,等额本金还款首月8,333.33元,以后每月递减17.36元。一般的,假设借款总额为T,年华利率为p,贷款年限为Y。

2.基本原理

房贷的利率是很厚道的实际利率,什么叫实际利率呢?就是按你实际占用银行资金的多少来计算利息。当你按月归还了一定的本金了以后,下个月计息的本金就变少了,而不像消费贷的分期付款,计息的本金一直是不变的,才出现实际利率比名义利率高很多的情况。无论是等额本息还是等额本金还款,利率都是实际利率,而按目前的商贷利率4.90%,公积金利率3.25%,甚至还有折扣,所以房贷是普通人能拿到大额低息贷款的最重要的方式。

按照实际利率,如果上一期还欠本金,年化利率为p,本期归还本金C,则本月须还款

M=C+T*p/12,下一期本金变为T-C。

3.等额本金还款

等额本金还款每个月还款数额逐渐减少,看起来比较麻烦,但是在原理和数学计算上其实更简单。首先,我们把借的本金T摊分到所有的月份,为,则首月还款为,T=1,000,000,p=5%,Y=20时,计算得到C=4166.67元,M=8333.33元,以后每月本金减少C,相应的利息减少,为17.36元。可以看到,等额本金还款每月还的本金不变,而利息则在不断减少。

4.等额本息还款

等额本息还款每个月还款数额相同,看起来比较简单,但是原理时数学计算更复杂,关键在于依然要符合2中所说的基本原理,随着待还本金的减少,每月还的利息会减少,但是要求每月归还的本金和利息加起来应该相同,这样的话,每个月归还的本金应该越来越多,才能维持这个平衡,究竟多多少,需要一个细致的计算过程。

我们知道最后一个月归还本金和利息后,贷款还完了,可以据此倒推。假设最后一个月还本金,则利息为,还款总额为,往前推一个月,假设这个月归还本金$M_{n-1}$,则利息为,归还总额为,由于,不难推出,一般的,由 得出

所以每月还款的本金是一个等比数列,它的比值比率是,简单起见,我们计算最后一个月的本金,则

,则,每月还款额度为,第一个月还款,以后每月等比增加,T=1,000,000,p=5%,Y=20,计算得到C=6,599.56,其中第一个月归还本金为2432.89元,每月等比增加1.0041667倍。

5 比较与提前还款

由于等额本金与等额本息还款方式的利率都是实际利率,所以在资金效率上,两者其实没有任何差别,网上有人分析说等额本息还款刚开始还的利息多本金少,所以提前还款相对等额本金的提前还款不划算,我认为是没有道理的,因为银行始终是按你实际占用的本金额度来收取利息的,而提前还款则是将余下的本金一次性还完。而两种贷款方式的选择,乃至是否提前还款,都不影响资金效率,那么该如何选择呢?

首先比较一下等额本金和等额本息,等额本金刚开始还款多,以后还款少,其中归还本金每月固定,而等额本息始终还款数额一样,其中归还本金每月增多,选择哪种方式,取决与你的工资收入水平以及占用资金后资金的投资效率,首先,如果你现在收入少,估计以后收入会不断增长,那么为了减轻现在的负担,自然是刚开始少还一点好,这时建议等额本息,而如果你现在收入高,以后还很难说,那么建议等额本金。但是如果你虽然现在钱很多,但是你的投资收益要高于贷款利率,那么还是建议等额本息,这样你能更多更久的占用银行资金来赚取利率差。

实际上如果你够钱全款买房,但是投资水平超过房贷利率,那么使用房贷依然是一个很好的选择,这种低息高额贷款是很难得的,而哪些炒房团,往往也是通过房贷负债加杠杆迅速的增长自己的财富的。

涉及到提前还款也是如此,如果你当下的投资收益率高过贷款利率,那么没有必要提前还款,反之投资收益率低于贷款利率,则建议提前还款,这跟等额本金或等额本息其实没什么关系。

《大护法》:恶趣味的1984

大护法

知道这部电影,是看到有微信公众号在含沙射影的批判这部电影,我很是好奇,一部打了龙标的电影,怎么可能政治不正确。

看完之后,倒是觉得导演的恶趣味很有意思,比如一个披上红色披风像个冬瓜,爱碎碎念,动不动就背诗的主角,模仿虫族的花生人设定,一个文艺范长得像徐锦江老师的太子,当然还有很明显模仿法西斯束棒的武器。

其实电影的作者究竟怎么想的不重要,电影是幻想的艺术,如果能触发观众的想象和分析,就是成功的。观众要怎么去想,则是一个很有意思的事情,正所谓智者见智仁者见仁淫者见淫,与其说一部动画电影能探讨点什么,不如说它激发了大家关心的话题,这种意想不到的气场的出现,估计以后还会屡见不鲜。

反乌托邦的文艺作品不鲜见,《1984》随时你都可以去看,即使是电影市场,去年的《驴得水》我觉得也可以归为这一类。这部电影其实更独特的是它的风格,虽然能看出一些不成熟的地方,比如太子和大护法对嘴吵架时画面非常崩坏,但是总算是脱离了简单叙事,正义战神邪恶的范畴。水墨风格的画面透着一种诡异的美感,碎碎念的台词,一旦接受了这种设定,就觉得冷幽默,而把电影变成儿童不宜的,这是随时爆头、喷血的场面,而剧本的设定处处透着诡异,即使到结局有些地方还是云里雾里,但是又蛮适合脑补。

希望能看到导演的续集。

偶像

今天傍晚客厅的电视放着《楚乔传》,因为想让着急同学安静一会儿,最近发现他看到电视里的漂亮姐姐时比较安静,我突然想到,着急同学以后会喜欢什么样的偶像明星是一件很有趣的事情。

有教育学的研究成果表明,对孩子影响最大的可能不是父母,而是他的同龄人,在小学生中,喜欢什么大多是一阵风,是一种集体共识。当下来看,八零九零乃至更年长的人群是打造偶像的主力,但是偶像的主力消费者却是更年轻的零零后,往往都是一群有文化的在给一群没文化的创造。

偶像的选择,看起来是自由意志,但是实际情况可能很复杂,首先偶像的选择其实是有国家意志在的,八九十年代的时候,中日关系很不错,像我堂哥就爱在卧室贴酒井法子的照片,而我父母也都知道不少日本明星的名字,后来中日关系恶化后,就开始引进韩国明星了,现在和韩国关系也不好,“国家面前无欧巴”,连我是歌手代表世界化的重任也交到了哈萨克斯坦人身上,又或者我们下一波可以哈一下泰国之类的,至于港台明星,都得学会好好说话,赞颂社会主义,才能在大陆揾食。不知道着急同学在追星的年纪,我国会和什么国家比较友好。

其次,偶像的选择也是一种集体认知,如果你要当一个随大流的好孩子,就不能喜欢太过奇怪的偶像,比如喜欢一个太老的演员或歌手,即使是喜欢小鲜肉,大抵也是要争夺话语权的。在互联网时代,这个问题变得有些奇怪,首先是长尾效应导致不管你喜欢得人有多奇怪总能找到共鸣,而且一般来说网上交流也不限年龄,另一方面,所谓粉丝的力量也得到了互联网的加强,原本只在学校风行的东西,现在在互联网上所向披靡——惹到粉丝总是吃力不讨好的,谁也不喜欢被一帮内心真诚而火热的人怒骂。

最后,偶像的选择是被媒体操纵的,偶像顾名思义外貌是及其重要的,而外貌最出众的人大多是搞文艺的,而且他们的工作又主要是在媒体上晃悠,“爱美之心,人皆有之”,也难怪着急同学爱看赵丽颖了,而美女科学家首先是数量少,再者她们也没时间整天再在媒体上晃悠,所以文艺工作者还真是有着不小的影响力,如果他们以身作则,大概是能对年轻人起到好的导向作用的,而一旦平行败坏,还要粉丝去维护形象,还真是腐坏社会风气。

总而言之,要想影响孩子的偶像选择,是一个复杂的系统工程,需要你拓宽他的视界,让他知道更多优秀的人,才能做出更加自由的选择。