发表于 | 分类于 |

1.Python命令行

在linux下输入python（windows下点击开始->程序->Python 2.3 ->IDLE（Python GUI）
在>>>提示符后输入print(‘Hello World!’)

Hello World!

2.Python小程序

用文本编辑器写一个.py结尾的文件，比如说helloWorld.py中写入print(“Hello World”) 在命令提示符中输入Python helloWorld.py，会在窗口中显示以下结果

Hello World!

3.Python脚本

下面将刚才的Python小程序改写成Python脚本

#!/usr/bin/env python
print("""Hello World!""")

更改helloWorld.py文件的权限

sudo chmod 755 helloWorld.py

输入./helloWorld.py即可之行该脚本，输入结果如下

Hello World!

知识点：

1.单引号、双引号、多引号的区别

*先说双引号与3个双引号的区别，双引号所表示的字符串通常要写成一行如果要写成多行，那么就要使用\ (“连行符”)

1
2
3
s1 = "hello,world"                 # s2与s1是一样的。
s2 = "hello,\
   world"

如果你用3个双引号的话，就可以直接写了，如下：

1
2
3
s3 = """hello,                      #s3实际上就是"hello,\nworld,\nhahaha.", “\n”是换行符。
world,
hahaha."""

如果你的字符串里\n很多，你又不想在字符串中用\n的话，那么就可以使用3个双引号。而且使用3个双引号还可以在字符串中增加注释，如下：

1
2
3
4
5
6
7
8
s3 = """hello,                      #hoho, this is hello, 在3个双引号的字符串内可以有注释哦
world,                              #hoho, this is world
hahaha."""
另外，三个引号还可用于注释。例如：

"""
大家好，我是注释
"""

  • 单引号与双引号的作用是相同的。但是为什么要引入单引号和双引号呢？
    举个例子：
    当我用单引号来表示一个字符串时，如果要表示 Let’s go 这个字符串，必须这样：

    s4 = 'Let\'s go'

    注意没有，字符串中有一个’，而字符串又是用’来表示，所以这个时候就要使用转义符 \ （\，转义符应该知道吧）, 如果你的字符串中有一大堆的转义符，看起来肯定不舒服python也很好的解决了这个问题。
    如下：

    s5 = "Let's go"

    这时，我们看，python知道你是用 “ 来表示字符串，所以python就把字符串中的那个单引号 ‘ , 当成普通的字符处理了，是不是很简单？
    对于双引号，也是一样的，下面举个例子

    s6 = 'I realy like "python"!'

    这就是单引号和双引号都可以表示字符串的原因了。

2.在Python 2.x中，print还可以是一个关键字，可写成print ‘Hello World!’，但这在3.x中行不通。

3.“#!/usr/bin/python”与”#!/usr/bin/env python”的区别（windows用户可以无视）

#!/usr/bin/python 是告诉操作系统执行这个脚本的时候，调用/usr/bin下的python解释器；相当于写死了Python的路径，如果Python的路径改变，脚本将无法执行。不推荐使用

#!/usr/bin/env python 这种用法是为了防止操作系统用户没有将python装在默认的/usr/bin路径里。当系统看到这一行的时候，首先会到env设置里查找python的安装路径，再调用对应路径下的解释器程序完成操作。

4.如何通过直接输入helloWorld.py而不是./helloWorld来执行脚本？（windows用户请无视）
在一般用户下输入PATH=$PATH：(注意后面的冒号)。 即可直接通过输入helloWorld.py执行脚本。
但是值得注意的是，千万不要用这种方法修改超级用户（一般是root）的PATH变量。这是一个安全网面 的漏洞，因为root用户管理员可能因此执行一个某个命令的伪装版本。

5.如何使你的程序在任何位置执行？

PATH=/home/userName/test:$PATH                             //将/home/userName/test加入PATH （注意中间的冒号！ PATH必须大写！）
sudo cp helloWorld.py /home/userName/test/helloWorld

然后输入helloWorld即可直接之行脚本

6.Python的注释

1
2
3
4
5
6
7
8
9
#单行注释

<**
多行注释1
**>

"""
多行注释2
"""

发表于 | 分类于 |

只学习过C语言也是可以做作品来参加code dream，这是面向计院全体大一新生的比赛，所以无需发怵，六队的学弟学妹也要做的66666！

参赛作品要求

本次比赛主要分为三个项目：网页设计类、程序软件类、算法设计类。各类别参赛作品具体要求如下：

（1）网页设计类

参赛选手自定一个站点名称，动态或静态网页不限，但演示成果要生成静态网页格式html。要有一定的代码量，不能直接套用动态网页生成程序来生成静态页面。要求主题鲜明突出，创意新颖，页面结构美观。制作软件不限制，通过合理运用网页设计的各种技术，体现良好的艺术性和实用性。页面深度必须在三层左右，以4-7个页面为宜。要求能在WinXP以上系统运行，显示分辨率800*600以上，网页采用Internet Explorer6.0以上浏览器。

例如：个人博客，宣传页面，简单网页应用（实现一定的功能，不受页面深度限制）等。

  • 个人博客可以使用成熟的WordPress，Z-blog，hexo等博客程序构建，然后自定义其部分功能，创建新的页面，要有独创性；
  • 宣传页面即介绍某个企业，产品，或者是其他你想让人知晓的页面，可以用Dreamwave，甚至是十几年前的frontpage(曾在小学课本里看到)，so easy；
  • 网页应用可以使用一些网络服务接口来创建自己的应用，最好有一定实际价值。
    参考 html瞬间入门

（2）程序软件作品

制作要求：具有一定实用价值或者娱乐价值，界面尽可能友好，使用简单，可以带有使用帮助。作品大概有这几个方面：信息管理、游戏娱乐、文体健康、学习生活等主题，内容务必积极健康向上。

例如：实用小工具，游戏，学习辅助软件等。

这是我最推荐你们去选择的题目。可以做计算器，小游戏，画图板等等。

  • 用c配合VC是可以实现图形界面的，具体会用到MFC，这个框架我并不熟悉，可以参考网上的资料自学，也可以向我索取；
  • 还有就是使用第三方的图形库，如文档很全的EGE,我曾用它实现过贪吃蛇；
  • 如果你想使用python我也是十分的支持，因为python太强大了。而且pygame是可以速成的，去找本《pygame游戏编程入门》看看，一个月做出很耐玩的游戏并不是很困难；
  • 还有一些歪门邪道的方式去做一个程序作品，我就不提了。
  • 其实，黑框框（控制台程序）也完全没问题，重要的是内涵。

（3）算法设计类

制作要求：利用算法解决已有的或与学习生活相关的复杂问题，算法具有一定的实现难度，体现出对编程语言和简单算法的掌握。要求配有算法流程图、必要的说明，能够以简单、直观的界面展示。

例如：矩阵计算，高等数学涵盖的计算，智能扫雷算法、五子棋人机对弈等。

不必多说，重在算法，对其他没什么特别的要求。

当然，你们能做的绝不局限于我说的这些，要开动脑筋，一旦有你想做的的东西，技术问题不会成为你最大的阻碍。有了C语言的基础，花上五六天去掌握一门新的编程语言也不是没有可能的。

发表于 | 分类于 |

引子

棋盘覆盖问题采用的是分治策略。通过十字划分，将原问题转化为四个规模较小的棋盘覆盖问题。递归的使用这种分割，将问题最简化。

问题简述

在一个 2^k 2^k个方格组成的棋盘中，若恰有一个方格与其它方格不同，则称该方格为一特殊方格，称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有 4^k 种情形。因而对任何 k>=0 ，有 4^k 种不同的特殊棋盘。下图所示的特殊棋盘为 k=2 时 16 个特殊棋盘中的一个。在棋盘覆盖问题中，要用下图中 4 中不同形态的 L 型骨牌覆盖一个给定的特殊棋牌上除特殊方格以外的所有方格，且任何 2 个 L 型骨牌不得重叠覆盖。易知，在任何一个 2^k 2^k 的棋盘中，用到的 L 型骨牌个数恰为 (4^k-1)/3 。

题解

用分治策略，可以设计解棋盘问题的一个简捷的算法。
当k>0时，将2^k 2^k棋盘分割为4个2^(k-1) 2^(k-1)子棋盘，如下图所示。

特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小的棋盘的汇合处，如下图所示，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题化为4个较小规模的棋盘覆盖问题。递归的使用这种分割，直至棋盘简化为1x1棋盘。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>

using namespace std;

int tile=1;     //L型骨牌的编号(递增)
int board[100][100];    //棋盘
/*****************************************************
* 递归方式实现棋盘覆盖算法
* 输入参数：
* tr--当前棋盘左上角的行号
* tc--当前棋盘左上角的列号
* dr--当前特殊方格所在的行号
* dc--当前特殊方格所在的列号
* size：当前棋盘的:2^k
*****************************************************/
void chessBoard ( int tr, int tc, int dr, int dc, int size )
{
    if ( size==1 )    //棋盘方格大小为1,说明递归到最里层
        return;
    int t=tile++;     //每次递增1
    int s=size/2;    //棋盘中间的行、列号(相等的)
    //检查特殊方块是否在左上角子棋盘中
    if ( dr<tr+s && dc<tc+s )              //在
        chessBoard ( tr, tc, dr, dc, s );
    else         //不在，将该子棋盘右下角的方块视为特殊方块
    {
        board[tr+s-1][tc+s-1]=t;
        chessBoard ( tr, tc, tr+s-1, tc+s-1, s );
    }
    //检查特殊方块是否在右上角子棋盘中
    if ( dr<tr+s && dc>=tc+s )               //在
        chessBoard ( tr, tc+s, dr, dc, s );
    else          //不在，将该子棋盘左下角的方块视为特殊方块
    {
        board[tr+s-1][tc+s]=t;
        chessBoard ( tr, tc+s, tr+s-1, tc+s, s );
    }
    //检查特殊方块是否在左下角子棋盘中
    if ( dr>=tr+s && dc<tc+s )              //在
        chessBoard ( tr+s, tc, dr, dc, s );
    else            //不在，将该子棋盘右上角的方块视为特殊方块
    {
        board[tr+s][tc+s-1]=t;
        chessBoard ( tr+s, tc, tr+s, tc+s-1, s );
    }
    //检查特殊方块是否在右下角子棋盘中
    if ( dr>=tr+s && dc>=tc+s )                //在
        chessBoard ( tr+s, tc+s, dr, dc, s );
    else         //不在，将该子棋盘左上角的方块视为特殊方块
    {
        board[tr+s][tc+s]=t;
        chessBoard ( tr+s, tc+s, tr+s, tc+s, s );
    }
}

void main()
{
    int size;
    cout<<"输入棋盘的size(2^n): ";
    cin>>size;
    int x,y;
    cout<<"输入特殊方格位置坐标: ";
    cin>>x>>y;
    chessBoard ( 0,0,x,y,size );
    for ( int i=0; i<size; i++ )
    {
        for ( int j=0; j<size; j++ )
            cout<<board[i][j]<<"\t";
        cout<<endl;
    }
}

EGE演示程序

我自己用EGE做了一个图形化演示，但效果并不理想，代码核心内容如上，就不贴代码了。如图

发表于 | 分类于 |

先决条件很简单，树莓派或是其他开发板甚至是LinuxPC，路由器。

我使用的是一代树莓派b+，内存512M加上超频到极限的单核处理器，实在是无法与树莓派2相媲美，不得已只好选择相对轻量的环境完成这项尝试。说道Web服务器，大家也许都会想到 Apache、MySql 等等，非常常见的组合LAMP（Linux+Apache+Mysql/MariaDB+Perl/PHP/Python） ，但是考虑到树莓派的性能有一个非常合适的组合 nginx + sqlite + php对了还有php博客程序，我选择Z-blog。

首先，要搭建一个Web服务器：

介绍一下 nginx 是个轻量级的高性能Web服务器，并不比Apache差，好像淘宝就广泛的使用它。
sqlite 是个非常轻量级的数据库，常用于嵌入式领域，许多Android应用用的也是它。
php 非常常用Web脚本语言，就不必介绍了。

不如直接切到root下工作

安装nginx web服务器 (约6MB)

1
sudo apt-get install nginx

启动nginx

1
sudo /etc/init.d/nginx start

nginx的www根目录默认在 /usr/share/nginx/www中，稍后的blog程序可以放到该目录下

安装php和sqlite(约9MB)

1
sudo apt-get install php5-fpm php5-sqlite

修改nginx的配置文件

1
sudo nano /etc/nginx/sites-available/default

找到listen行，将其前面的#号注释去掉，修改后内容如下

1
listen 80; ## listen for ipv4.

在路由器的内网环境下80端口并不是一个好的选择，因为绝大多数路由器不会开放例如80这样的常用端口，我设置成8888，看个人爱好咯

找到index行，加入index.php，修改后内容如下

1
index index.php index.html index.htm

找到php的定义段，将这些行的注释去掉 ，修改后内容如下

1
2
3
4
5
location ~ \.php$ {
fastcgi_pass unix:/var/run/php5-fpm.sock;
fastcgi_index index.php;
include fastcgi_params;
}

重新加载nginx的配置

1
sudo /etc/init.d/nginx reload

上面的操作很关键，是通用的步骤，但没接触过nginx的我在其中栽了好多跟头

检验一下

接下来我们访问一下试试，我的树莓派静态ip地址是 192.168.1.110（一定要设置好），刚才设置了监听端口8888，浏览器访问 192.168.1.110:8888

出现Welcome to nginx!

说明我的nginx服务已经启动成功。

然后在树莓派中生成一php文件，测试一下php

1
sudo nano /usr/share/nginx/www/test.php

在文件中输入以下内容

1
<?  phpinfo(); ?>

Ctrl+X然后Yes存盘退出

再来访问一下，PHP OK

出现PHP页面

使你的树莓派能够从外网访问：

你得申请一个免费的动态域名解析，由于我用的是ＦＡＳＴ的路由器，只支持花生壳，所以我申请了花生壳的动态域名解析。申请花生壳很简单，打开 http://www.oray.com ,点击顶部的“注册”，申请一个花生壳域名。

有很多二级域名可以选择

i ok la是不是很好记

进入路由器，配置你的花生壳动态域名账号，别忘了DDNS，否则登不上，点击登录，保存

大部分国产路由器都支持花生壳，记得Tenda不支持

接下来需要配置端口了。先要确定你的树莓派在局域网内的IP，给它一个静态的IP：192.168.1.110

然后添加端口转发，到192.168.1.110，刚才的8888端口保证她是生效的，也可以继续添加一些其他端口便于管理。

22,443端口都可以开启

现在可以试着用外网访问一下 你的花生壳域名，别忘了加上“:”+端口号。

到这里基本上已经大功告成，只消几分钟你的blog就可以运作起来了。

Blog程序安装:

选用同样轻量的Z-blog，完美支持我们前面搭建的平台；如果使用WordPress未尝不可，但是它不完全支持sqlite，可以参考（http://www.tuicool.com/articles/fuiyQb ）。

简单说过一下吧！太困了

进/usr/share/nginx/www/下，

1
wget https://github.com/zblogcn/Release/raw/master/zip/Z-BlogPHP_1_4_Deeplue_150101.zip

解压

通过浏览器访问Release下的index.php或者install.php进入安装步骤，后面就一路点下去,后台出现

大功告成

我的主页 http://bwael.iok.la:8888/ 近期会一直开放

原文是有图的 : 原文

发表于 | 分类于 |

引子

开学第一周，初识算法课，当头一棒，老师NP 问题云云，遂寻书溯源，不得解。

突然发现《计算机算法设计与分析》这本书真是过分啊，整一册习题集，不只是哪位老师运用腾挪大法著成此书，怕了怕了。去借学神的《算法导论》一睹NP真容。

……欢迎批评指正

NP

我们以前接触的算法基本上都是多项式时间算法：对于规模为n的输入，在最坏的情况下的运行时间是O(n^k)，其中k为某一确定常数。 但实际上有一些问题不能在多项式时间内解决；另外，还有许多可以在多项式时间内解决的问题，但对任意常数k，它们都不能在O(n^k)时间内被解决。

上面所提的后者在我的理解中就是NP问题。可以这样想想：对于下一步的动作，他们也不知道确切的应该怎么办，只能“尝试”很多种方案才能够得出一个答案，这显然是很费时的。

至于NPC问题，可以这么认为，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。

……

总之，当我们试着去说明一个问题为NP完全问题时，我们是在陈述它是一个多么困难的问题，并不是去证明它存在某个有效算法，而是去证明不太可能存在有效的算法去解决问题。

NP问题的存在，应该就是提醒我们对待复杂的问题，更好的办法是花时间开发一种近似算法或解决某种已处理问题的特例，而不是寻找求得问题确切解的一种快速算法。

递归策略

直接的或间接的调用自身的算法称为递归算法。

递归的使用在我的印象中最深刻的是初学时完成的求n的阶乘 程序：

1
2
3
4
5
int factorial (int n)
{
    if(n==1)   return 1;
    return  n*factorial(n-1)
}

未完待续