用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: Program
Tags: No Tags
Comments: 1 Comment
Published on: 2012/11/28

若干年前在电子bbs【自由空间】上的一个题目,来源链接:http://thuee.net/bbscon.php?bid=13&id=64451

假设有一个数组P有3N+1个整数,其中有N个数每个出现3次,还有一个特殊数仅出现过一次,比如{a,a,a,b,b,b,c}。要求只遍历一遍数组将这个数找出来,空间复杂度O(1)。

如果是每个数只出现两次,那么只需要把所有的数异或起来就可以得到最终的结果了。那出现三次呢?下面这个程序巧妙地实现了这一点:
(more...)

看到一段很喜欢的程序

Categories: Program
Tags: No Tags
Comments: 2 Comments
Published on: 2012/10/05
#include <stdio.h>
void main() {
    double sided;
    unsigned letter;
    short happiness;
    long memories;
    printf("I love you.\n");
}

来源:http://www.guokr.com/group/posts/60/

天平称球问题的推广

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来说应该是一个比较令人兴奋的事情,但是我觉得现在这个系统还不够成熟。没准以后可能真有一个能够保证交易公平的虚拟化货币,还是很值得期待的。

清华百年校庆献礼——Matlab版老校歌

Categories: Program
Tags: No Tags
Comments: 2 Comments
Published on: 2011/04/21

当年上matlab课,要写个生成音乐的程序,我就写了这个老校歌。当时大作业里面的“电灯比油灯进步多了”那一段用于语音处理的音频想必很多电子系的兄弟姐妹记忆犹新吧。
当时交上去的版本其实还有很多我不满意的地方,某一年翻出来又给改了一下,用了shenhuanyan mm的某个程序里面的音色,修改了音符的轮廓,加了个颤。另外和声是依照的是何一林夫人版合唱谱。

没有matlab的同学可以直接听这个wav文件:Matlab老校歌

新的版本我还是比较满意的,程序如下 (保存为playlxg.m即可):

?View Code MATLAB
%% play "老校歌"
%% written by vichare@vichare.net
function y = playlxg()
global lxg;
if length(lxg) < 5;
    rhythm1 = [1 1 3 5 5 6 1 6 5 5 3 3 5 3 1 6 1 3 5 6 6 6 1 5 3 2 3 2 1 2 5 5 14 5 6 6 7 6 5 1 1 6 1 5 6 5 6 6 5 3 2 2 3 5 1 1 1 3 2 3 2 1 6 6 5 3 2 2 3 1 1 1 6 6 5 5 6 5 2 3 5 1 1 6 6 5 5 6 5 2 3 2 1;
    0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0;
    1 0.5 0.5 1 1 1 0.5 0.5 1 1 1 1 0.5 0.5 1 1 0.5 0.5 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 1 0.5 0.5 4 1.5 0.5 1 1 1.5 0.5 2 1.5 0.5 1 1 1 0.5 0.5 2 1.5 0.5 1 1 1 0.5 0.5 2 1.5 0.5 1 1 1 0.5 0.5 2 1 3 1 3 1 1 1 1 1 1 2 1 3 1 3 1 1 1 1 1 0.5 0.5 2];
    rhythm2 = [5 1 3 3 6 6 5 5 1 1 3 1 5 6 6 1 7 4 4 4 3 1 7 1 7 1 7 2 2 2 1 1 1 7 3 3 4 4 3 4 3 4 1 2 1 7 7 1 7 5 5 5 1 7 7 5 1 1 2 1 7 7 5 3 3 1 1 3 3 4 2 7 1 7 3 3 1 1 3 3 4 2 7 7 5;
    -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 0 -1 0 0 0 0 0 -1 0 -1 0 -1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 -1 -1 -1 -1 0 -1 -1 -1 0 0 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 -1 0 -1 0 0 0 0 0 0 0 0 -1 -1 -1;
    1 1 1 1 1 1 1 1 1 1 0.5 0.5 1 1 0.5 0.5 2 1 1 1 1 1 1 0.5 0.5 1 1 1 1 1 1 1 1 4 1.5 0.5 1 1 1.5 0.5 2 1.5 0.5 1 1 1 0.5 0.5 2 1.5 0.5 1 1 1 1 2 1.5 0.5 1 1 1 1 2 1 3 1 3 1 1 1 1 1 1 2 1 3 1 3 1 1 1 1 1 1 2];
    rhythm3 = [3 3 5 1 1 6 6 1 1 5 5 1 5 3 14 4 4 5 1 1 1 6 1 5 5 5 4 3 5 7 7 7 14 4 4 5 5 5 1 1 1 1 1 1 4 5 5 5 5 5 3 3 3 5 5 4 3 4 4 5 5 5 4 3 5 5 4 4 1 1 1 7 5 5 5 5 5 4 4 1 1 1 7 5 5 4 3;
    0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0;
    1 0.5 0.5 1 1 1 1 1 1 1 1 0.5 0.5 1 1 0.5 0.5 2 1 1 0.5 0.5 1 1 1 0.5 0.5 1 1 1 1 1 1 1 1 4 1.5 0.5 1 1 1.5 0.5 2 1.5 0.5 1 1 1 1 2 1.5 0.5 1 1 1 1 2 1.5 0.5 1 1 1 1 2 1 3 1 3 1 1 1 1 1 1 2 1 3 1 3 1 1 1 1 1 0.5 0.5 2];
    rhythm4 = [1 1 1 1 4 4 1 1 1 1 1 1 2 2 2 5 4 4 4 1 1 5 5 1 7 7 2 2 2 2 2 5 1 1 4 6 1 1 1 4 4 7 1 5 5 5 1 1 1 1 5 5 1 4 4 7 1 5 5 1 1 1 4 4 1 1 4 5 5 5 5 1 1 4 4 1 1 4 5 5 5 1;
    0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 -1 -1 0 -1 -1 0 0 0 0 0 -1 0 0 -1 -1 0 0 0 -1 -1 -1 0 -1 -1 -1 0 0 0 0 -1 -1 0 -1 -1 -1 0 -1 -1 0 0 0 -1 -1 0 0 -1 -1 -1 -1 -1 0 0 -1 -1 0 0 -1 -1 -1 -1 0;
    1 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0.5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1.5 0.5 1 1 1.5 0.5 2 1.5 0.5 1 1 1 1 2 1.5 0.5 1 1 1 1 2 1.5 0.5 1 1 1 1 2 1 3 1 3 1 1 1 1 1 1 2 1 3 1 3 1 1 1 1 1 1 2];
    y1 = generaterhythm(rhythm1, 3); % in bE tune
    y2 = generaterhythm(rhythm2, 3); % in bE tune
    y3 = generaterhythm(rhythm3, 3); % in bE tune
    y4 = generaterhythm(rhythm4, 3); % in bE tune
    %plot(y);
    lxg = (y1+y2+y3/2+y4/2)/3;
    sound(lxg); % play it!
    %wavwrite(lxg, 8000, 'lxg.wav'); % write to file
else
    sound(lxg); % play it!
end
 
%% generate a piece of rhythm
function y = generaterhythm(rhythm, basetune)
% GENERATERHYTHM function.
% rhythm is a 3 * len matrix
% for each column, the element on the first row
% shows the 'sound name' of one tune, the one
% on the second row shows the sound step of that tune,
% and the one on the third row shows how long
%in seconds it should lasts.
fs = 8000;
soundpos = [0 2 4 5 7 9 11 0:12];
y = zeros(1, sum(rhythm(3,:))*fs + 1); % initialize
curpos = 1;
for count = 1 : length(rhythm)
cursoundname = rhythm(1, count);
cursoundpos = soundpos(cursoundname);
curfreq = 220 * 2 .^ ((cursoundpos + basetune + 3) / 12 + rhythm(2, count));
cursound = generatetune(curfreq, rhythm(3, count), fs);
y(1,curpos:(curpos + length(cursound) - 1)) = cursound;
curpos = curpos + length(cursound);
end
 
%% generate a piece of sound with the frequence of freq
function y = generatetune (freq, time, fs)
y1 = generatetune2 (freq + 3, time, fs);
y2 = generatetune2 (freq - 3, time, fs);
y3 = generatetune2 (freq, time, fs);
y = (y1 + y2) / 8 + y3 * (3 / 4);
 
%% generate a piece of sound with the frequence of freq
function y = generatetune2 (freq, time, fs)
c = [ 1 0.2 0.4 0.08 0.2 0.05 0.1 0.04 ];
t = 0:1/fs:(time - 1/fs);
y = zeros(1, length(t));
for k = 1 : 8
    y = y + c(k) * sin(t*k*freq*2*pi);
end
%%y = 0.6 * sin(t*freq*2*pi) + 0.1 * sin(t*freq*4*pi) + 0.2 * sin(t*freq*6*pi);
for count1 = 1 : length(y)
    y(1, count1) = y(1, count1) * amendment(count1 / 2000, length(y) / 2000);
end
 
%% amendment of the shape of the wave
function y = amendment(p, l) % 0 <= p <= 1
if p < 0.2
y = p * 5;
elseif p < 0.3
y = 1.8 - p * 4;
else
    y = 0.6 * exp((0.3 - p)/5);
%%elseif p < (l - 0.2)
%%y = 0.6;
%%else
%%y = (l - p) * 3;
end

转载新闻二则: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的问题。果然关了之后就好了,多了几条垃圾评论。

«page 1 of 6
Welcome , today is Wednesday, 2016/12/07