安装git以及clone repo

Categories: Uncategorized
Tags: No Tags
Comments: No Comments
Published on: 2017/01/28

继续流水账记录一下安装过程。
先装git
$ sudo apt-get update
$ sudo apt-get install git

稍微配置一下
$ git config --global user.name "Your Name"
$ git config --global user.email "youremail@domain.com"

配置ssh key
$ ssh-keygen -t rsa -b 4096 -C "your_email@example.com"
按提示输入信息,然后
$ eval "$(ssh-agent -s)"
$ ssh-add ~/.ssh/id_rsa

最后把public key(默认是~/.ssh/id_rsa.pub)存到git server就可以了。

装个git prompt这样命令行前缀能显示更多的信息:

$ cd ~
$ git clone https://github.com/magicmonty/bash-git-prompt.git .bash-git-prompt --depth=1
$ cat <> ~/.bashrc
   # Set config variables first
   GIT_PROMPT_ONLY_IN_REPO=1

   # GIT_PROMPT_FETCH_REMOTE_STATUS=0   # uncomment to avoid fetching remote status

   # GIT_PROMPT_SHOW_UPSTREAM=1 # uncomment to show upstream tracking branch
   # GIT_PROMPT_SHOW_UNTRACKED_FILES=all # can be no, normal or all; determines counting of untracked files

   # GIT_PROMPT_SHOW_CHANGED_FILES_COUNT=0 # uncomment to avoid printing the number of changed files

   # GIT_PROMPT_STATUS_COMMAND=gitstatus_pre-1.7.10.sh # uncomment to support Git older than 1.7.10

   # GIT_PROMPT_START=...    # uncomment for custom prompt start sequence
   # GIT_PROMPT_END=...      # uncomment for custom prompt end sequence

   # as last entry source the gitprompt script
   # GIT_PROMPT_THEME=Custom # use custom theme specified in file GIT_PROMPT_THEME_FILE (default ~/.git-prompt-colors.sh)
   # GIT_PROMPT_THEME_FILE=~/.git-prompt-colors.sh
   # GIT_PROMPT_THEME=Solarized # use theme optimized for solarized color scheme
   source ~/.bash-git-prompt/gitprompt.sh
EOF

Ubuntu环境下安装scrapy

Categories: Uncategorized
Tags: No Tags
Comments: No Comments
Published on: 2017/01/22

[这里应有前言]

在刚装好的ubuntu下,默认已经装好了python:
~$ python --version
Python 2.7.6

安装pip:
$ sudo apt-get update
$ sudo apt-get install python-pip

这个时候直接用"sudo pip install scrapy"会报错,错误信息是
Could not find function xmlCheckVersion in library libxml2. Is libxml2 installed?

根据安装指南,需要安装好以下程序:

参考Stack Overflow
$ sudo apt-get install libxml2-dev libxslt1-dev python-dev
如果python 版本Python 2 >=2.7.9 或者 Python 3 >=3.4,默认已经安装了setuptool,但是还是必须升级一下:
$ pip install -U pip setuptools
这个时候可以
$ pip install scrapy
了。
这时候如果报openssl的错,可能需要安装一下:
$ sudo apt-get update && sudo apt-get install libssl-dev

如果需要装beautiful soup:
$ pip install beautifulsoup4

用Vim撰写latex文档

Categories: Uncategorized
Tags: No Tags
Comments: No Comments
Published on: 2014/02/25

最近经常需要用latex写论文,于是折腾了一下vim-latex插件,在这里记录一下。

环境是 Windows 7 系统,需要安装Vim,Vundle插件,vim-latex插件,git (for Vundle).
(more...)

天平称球问题的推广

Categories: Uncategorized
Tags: No Tags
Comments: 1 Comment
Published on: 2012/05/13

  天平秤球这个问题的各种版本在很多年以前就流传开了,我在2010年的时候曾经总结过一个结论比较强的版本:

  假设有13个外形完全一样的球,其中12个等重,剩下一个重量和其他的球不同,既可能更轻又可能更重。
1.能否用天平称3次找出那个重量不同的球;
2.能否用天平称3次找出那个重量不同的球,并且获知那个球比其他的球更轻还是更重
能则给出方案,不能则证明

(more...)

掷硬币问题

Categories: Uncategorized
Tags: No Tags
Comments: No Comments
Published on: 2011/07/11

这里讨论一个掷硬币问题:假如一个人要连续掷n (n>=1)次硬币,他可以掷大于或等于1的任意多次,并且可以随时决定是否停止。当他决定停止后,他会获得一定的收益,收益大小正比于掷硬币的结果中正面所占的比例。

例如:掷的第一次为反面,第二、三、四次都是正面。此时他认为得到的结果已经足够好了,决定停止。这次他的收益就为0.75。

另外还有个约束就是这个人的决策必须在期望有限的次数内停下。我们假设这个人足够聪明,采用最优策略使得收益的期望最大化。那么这个收益的期望是多少?最优策略是什么?

首先我们把这个问题符号化:
我们所做的决策,就是决定在什么时刻停止。假设某一状态下已经掷过m次硬币,其中有n次为正面(m >= n >= 0),条件期望收益函数f(m, n)表示在当前状态下得到收益的期望,那么该函数有如下递推表达:

f(m, n) = \max\{\frac{n}{m}, \frac{f(m+1,n+1) + f(m+1,n)}{2}\}

这个问题的难点在于f(m, n)的递推表达包含无穷多项。一种可行的数值解法是对问题中掷硬币的次数限制在N次以内。当N的值逐渐增大趋于无穷时,收益f(m,n;N)单调递增并趋于期望的收益。对于有限次数的问题可以通过动态规划算法求解,本文最后给出了我用C++写的数值计算程序。当N=1000000时,运算结果为0.792942。而且一个比较反直觉的例子是当连续掷三次出现两次正面的话仍然不应该停下来。

Ps: 这个问题是我在考虑一个信道估计的算法时抽象出来的一个问题的最简单情况。虽然转化成这个问题已经和原问题偏离很远了,但是感觉这个题目比较好玩,并且没有很显然的解,就在校内上提了出来。结果发现某姚班的同学在他的blog 阅微堂 中也提到过这个问题。
Ps2: 这里给出了数值计算并且进行了一定的优化。我的程序结果和他的数据略有出入,不清楚是因为有错误还是因为他的近似。100000的结果和阅微堂中的是吻合的。

#include <iostream>
#include <iomanip>
 
using namespace std;
 
const int buffersize = 1000002;
int maxnum;
long double buf1[buffersize + 1];
long double buf2[buffersize + 1];
long double *benefit = buf1;
long double *postbenefit = buf2;
long double *temp;
inline void swap() {
    temp = postbenefit;
    postbenefit = benefit;
    benefit = temp;
}
 
int main() {
    long double b1, b2, dm;
    cin >> maxnum;
    dm = (long double)(maxnum);
    for (int i = 0; i <= maxnum; i++) {
        // benefit[i] = f(maxnum, i)
        postbenefit[i] = (i * 2 < maxnum) ? 0.5 : ((long double)(i) / dm);
    }
 
    long long count = 0;
    long long all = (long long)(maxnum) * (maxnum + 1) / 2;
    long long percent = 1;
    long long nextstep = all / 100 * percent;
    for (int m = maxnum - 1; m >= 0; m--) {
        dm = (long double)(m);
        for (int i = 0; i <= m; i++) {
            ++count;
            if (count > nextstep) {
                nextstep = all * percent / 100;
                cerr << percent << "%" << endl;
                ++percent;
            }
            // postbenefit[i] = f(m+1, i)
            b1 = (long double)(i) / dm;
            // (f(m+1, i+1) + f(m+1, i)) / 2
            b2 = (postbenefit[i + 1] + postbenefit[i]) / 2;
            benefit[i] = (b1 > b2 ? b1 : b2);
        }
        swap();
    }
 
    cout << setprecision(10) << postbenefit[0] << endl;
 
    return 0;
}

关于bitcoin的个人想法

Categories: Uncategorized
Tags: No Tags
Comments: No Comments
Published on: 2011/06/20

仅凭少量的的资料和直觉,我并不喜欢这个东西,主要有几个理由:

1.不环保,耗能大。为了分布式地保证安全性,要进行大量的运算,甚至bitcoin本身就是运算的结果。虽然有人说其他金融系统的维护也要消耗大量的能源。但是根据我粗略地估算这两个可能不在一个数量级上。不知道有没有人有可靠一点的数据

2.不可人为调控。很多人似乎觉得这是好事,但我觉得隐藏着很多致命的问题。目前的bitcoin就像是一个宝库,总共就那么多金子,然后大家拼命地找,肯定越来越难找,然后越来越值钱。越来越值钱的东西大家都想囤着,然后就不流通,这还是货币么。

也有可能将来没那么值钱了,然后找金子的花费超过它的价值,然后就没人愿意去找了。但是呢,bitcoin的交易维护也要依赖于mining(找金子)的过程,所以没人找金子这个系统就崩溃了,所以大家都不傻,将来这个系统靠谁维护呢?

可怕的是这东西又不能认为调控,所以不稳定,谁也说不好将来会什么样

3.数据安全

文件没了什么都没了,而且没救。普通个人pc又不是银行数据库,谁成天备份还要保证各种安全啊。黑客入侵,物理介质损坏,这种问题总是在所难免。安全性我个人还是比较质疑的,比如这两天不就出黑客盗窃海量BTC的事件么。

4.涉嫌欺诈

按照现在的汇率,初始拥有bitcoin的人将会相当于拥有一笔相当可观的财富,这个叫做炒作也好,欺骗也好,我觉得比较不靠谱

上面这些分析呢,仅靠感觉和少量估算。其实有那么一个数字化虚拟货币对于一个geek来说应该是一个比较令人兴奋的事情,但是我觉得现在这个系统还不够成熟。没准以后可能真有一个能够保证交易公平的虚拟化货币,还是很值得期待的。

转载新闻二则:P≠NP有望得证 魔方问题告破

Categories: Uncategorized
Tags: No Tags
Comments: 1 Comment
Published on: 2010/08/10

来源:http://www.matrix67.com/blog/archives/3520

昨天的消息:一位 HP 的研究员 Vinay Deolalikar 宣称自己证明了 NP 问题,得出了 P≠NP 的结论。 P 是否等于 NP ,这是计算机科学领域中最困难的问题之一,也是意义最深远的问题之一,长期以来一直备受争议。如果这个问题获得解决,将会在各个科学领域中引起轰动。 Vinay Deolalikar 的整个证明有 100 多页,详细的论文可以在这里看到:

http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf

Stanford 的博士后 randomwalker 看完证明后表示,很多迹象表明,这个证明很有可能是正确的。

---------------------------

今天早晨的消息: Morley Davidson 、 John Dethridge 、 Herbert Kociemba 和 Tomas Rokicki 宣称,他们已经利用计算机,完美地解决了魔方问题。他们验证了,任何一种魔方的初始状态都可以在 20 步以内解出。他们将 43,252,003,274,489,856,000 种初始状态分为了 2,217,093,120 组,再利用对称性和集合覆盖将规模缩小到了 55,882,296 组。他们的程序可以在 20 秒左右求解出一组问题的解法,最终利用 Google 提供的强大的计算机,彻底解决了魔方问题。
利用组合数学,我们能够证明,存在一种魔方初始状态,它需要至少 18 步才能解决。 1995 年, Michael Reid 找到了一种最少需要 20 步才能获解的魔方初始状态,因而将魔方问题的下界提高到了 20 。此后,数学家们猜想,任意给定一个魔方的初始状态,最多 20 步就能解决。 2008 年, Tomas Rokicki 和 John Welborn 证明了,任意一个魔方初始状态都可以在 22 步以内解决。 2010 年 7 月,这个上界终于降低到了 20 ,从而完成了对魔方最优解问题数十年来的探索。
详细的研究成果见这里:

http://www.cube20.org/

简化版的优化问题

Categories: Uncategorized
Tags: No Tags
Comments: No Comments
Published on: 2010/07/02

提问:一个优化问题一文中提出了一个5种属性点的分配问题。如果n=2,并且假定没有主属性和副属性相同的技能,也就是只有两种属性,那么问题可以简化到很容易求出解析解。

问题描述:

\mathrm{min} \frac{A_1}{2p_1+p_2}+\frac{A_2}{p_1+2p_2}

\mathrm{s.t.}p_1+p_2=C, p_1, p_2 >= 0

定义F(p_1, p_2, \lambda) = \frac{A_1}{2p_1+p_2}+\frac{A_2}{p_1+2p_2}-\lambda(p_1+p_2)

\frac{\partial F}{\partial p_1}=-\frac{2A_1}{(2p_1+p_2)^2}-\frac{A_2}{(p_1+2p_2)^2}+\lambda=0\frac{\partial F}{\partial p_2} = -\frac{A_1 }{(2p_1+p_2)^2}-\frac{2A_2}{(p_1+2p_2)^2}+\lambda=0

那么有:\frac{A_1}{(2p_1 +p_2)^2}=\frac{A_2}{(p_1+2p_2)^2}

k= \sqrt{\frac{A_1}{A_2}},则:

k= \frac{2p_1+p_2}{p_1+2p_2}

So, \frac{p_1}{p_2}=\frac{2-k}{2k-1}

无题

Categories: Uncategorized
Tags: No Tags
Comments: No Comments
Published on: 2010/06/28

前一段时间发现blog未注册用户不能回复。询问了一下maoz同学,告知可能是Akismet的问题。果然关了之后就好了,多了几条垃圾评论。

提问:一个优化问题

Categories: Uncategorized
Tags: No Tags
Comments: 2 Comments
Published on: 2010/04/21

问题来源于网游:星战前夜的技能训练系统。
假定一个人物有n种属性点,特别的,n =5。设这n种属性的值分别为P_i, i=1,2,3,4,5。游戏中有若干技能,每种技能对应一种主要属性和一种次要属性。属性点初期可以自由分配,其总和为C ,即:C =\sum\limits_{i=1}^5P_i。技能按照主、副属性的类型分成 n^2 类,,其中主、副属性分别为i ,j的技能的总技能点数为 A_{i, j}。技能的训练时间和该技能的点数成正比,和主属性点数的2倍加上副属性点数的值成反比,即:T_{i,j}=\frac{A_{i,j}}{2P_i+P_j}。现在给定C  A_{i,j},求非负的 P_i,使得技能训练总时间T=\sum\limits_{i,j=1}^5T_{i,j}最短,即:
\mathrm{min} \sum\limits_{i,j=1}^5\frac{A_{i,j}}{2P_i+P_j}

s.t. \sum\limits_{i=1}^5P_i=C

P_i \ge 0 , i=1,2,3,4,5

PS:此帖是为了测试latex for wordpress

«page 1 of 5
Welcome , today is Wednesday, 2018/02/21