webdancer's Blog

Ubuntu 10.04 下django 部署到apache服务器

由于django自带的服务器,对静态的文件支持不好。所以,决定将django工程部署到apache服务器上,下面记录一下大致的过程。

1.安装apache服务器。

sudo aptitude search apache

搜索一下,安装:

sudo aptitude install apache2

2.安装插件。django与服务器连接有好几个插件,我用的是:mod_wsgi(http://code.google.com/p/modwsgi/).在10.04下:

sudo aptitude search apache|grep wsgi

搜索一下,安装:

sudo aptitude install libapache2-mod-wsgi 

3.配置。

我的工程位于Ubuntu主目录下面,根据django的文档:

1).apache配置。

编辑/etc/httpd.conf,

 

AliasMatch ^/([^/]*\.css) ~/bookmarks/media/$1
Alias /media/ ~/bookmarks/media/

<Directory ~/bookmarks/media>
Order deny,allow
Allow from all
</Directory>

WSGIScriptAlias / ~/bookmarks/apache/django.wsgi

/:程序url起始位置。

~/bookmarks/apache/django.wsgi:工程目录下,新建apache目录,建立django.wsgi文件。

2)编辑django.wsgi文件:

import os
import sys

sys.path.append('~')
sys.path.append('~/bookmarks')

os.environ['DJANGO_SETTINGS_MODULE']='bookmarks.settings'

import django.core.handlers.wsgi

application=django.core.handlers.wsgi.WSGIHandler()

参考:http://docs.djangoproject.com/en/1.2/howto/deployment/modwsgi/

http://code.google.com/p/modwsgi/wiki/InstallationOnLinux

记得,重新启动apache,

sudo apache2ctl restart

配置完成后,不知道为什么刚开始不行,刷了几次,就OK了。

0/1背包问题

问题:背包容量c,从n个物品中选取装入背包,每个物品i的重量为wi,价值pi。在背包中物品不超过c的条件下,求装入背包中的。

分析:采用动态规划算法,假设f(i , y):表示背包剩余容量为y,剩余物品为i,i+1,。。。,n。则状态转移方程为:

f(i , y)=max{f(i+1 ,y) , f(i+1 ,y-wi)+pi}  if y>=wi;  

f(i , y)=f(i+1 , y) if y<wi;

代码如下:

#include<stdio.h>

#define N 3
int w[N+1];
int p[N+1];

int max(int x ,int y){
    return (x>y)?x:y;
}

int maxf(int i,int y){
   if(i==N)
        return (y>=w[N])?p[N]:0;
   if(y<w[i])
       return maxf(i+1,y);
   else
       return max(maxf(i+1,y),maxf(i+1,y-w[i])+p[i]);
}

int main(){
    int c;

    c=116;
    w[1]=100;
    w[2]=14;
    w[3]=10;
    p[1]=20;
    p[2]=18;
    p[3]=15;
    printf("the max :%d\n",maxf(1,c));

    return 0;
}

时间复杂度:O($$2^n$$)。 

由于使用了递归,空间复杂度也很大。

子数组的最大和

 

题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
分析:由于数组里有正数也有负数,所以不存在全为负数情况;所以,依据+正数变大,+负数变小的原理。代码如下:
#include<stdio.h>

int maxsubarr(int a[],int n){
    int i,cur,max;
    
    cur=0;
    max=0;
    for(i=0;i<n;i++){
        cur+=a[i];
        if(cur>max)
            max=cur;
        if(cur<0)
            cur=0;
    }
    return max;
}

int main(){
    int a[]={-1,0,-2,1,2,3,4,-2,3,4,-1,2,4};
    int n=sizeof a/sizeof a[0];
    printf("the maxsum of the sub:%d\n",maxsubarr(a,n));

    return 0;
}

 

vim使用的问题列表

“工欲善其事,必先利其器”,作为使用vim也有一段时间了,我想总结一下我使用中的问题。

1.不知道如何使用帮助。

这应该是我接触计算机很晚,或者习惯问题,我不喜欢看help文档,直接从网上搜索。这种习惯,现在看来不好,使用一种软件,help文档是第一手资料,应该首先查看,vim的help文档写的很好。举个例子:我将源文件中的单词Charfield 写成了Charfeild。我记不清了如何替换,但是记着s打头。可以直接从文档里找到答案。

:help :s

学会帮助文档,也可以让我意识到在写软件时,文档的重要性。

2.跳转问题。

有时候,需要在源文件里面跳来跳去,只会h,j,k,l显然是不够的。

n shift g 

n:行号。可以跳到具体的行。有时候,需要在声明,实现之间跳来跳去,tag很好用。:

:set tags=tagfile
ctrl ]

3.复制、粘帖。

复制:nyy

粘帖:p or P

4.打开文件。

刚开始用的时候,竟然编辑另一个文件的时候,会先关上原来的。其实,很容易打开一个文件:

:e filename

5.更改权限。

我经常编辑系统配置文件时,忘记了打开root权限,这时候有个很好的解决方法:

:w !sudo tee %

6.括号匹配。

有时候,编辑深度很深的循环可能就很又用了。

%

7.查找。

/

8.替换。

很多时候,我们可能把函数名或变量写错了。这时候,替换很重要呀!

:[range]s/{pattern}/{string}/[falg]

10.撤销,重组。

u
ctrl r

11.查看man手册。

K

或者:首先,加载 man 文件类型的外挂:

:runtime! ftplugin/man.vim

如果你经常用到这种方法,可以把这个命令加到你的 vimrc 文件中。现在你可以用
":Man" 命令打开一个显示 man 手册的窗口了:
:Man csh
 
一把好剑,也得学会剑招呀!

拓扑排序2

    前一篇,学习了根据DFS,来进行拓扑排序的方法;今天看一下,按照贪婪算法来进行拓扑排序。主要的思想:找没有入度的顶点,放到队列里面;然后,逐渐从队列里删除顶点,加入一个数组,如果产生了新的没有入度的顶点,也加入队列,重复直到队列为空。

 

#include<stdio.h>
#include<stdlib.h>
#include"graph.c"
#include"queue.c"
#define MAX 100

int indeg[MAX];
int vl[MAX];
int *q;
void topolsort(Graph g){
    int i,nv;

    nv=g->nv;
    for(i=0;i<nv;i++){
        struct node * vnode;
        vnode=g->adj[i];
        while(vnode){
            int u;
            u=vnode->v;
            indeg[u]++;
            vnode=vnode->next;
        }
    }
    q=initq(nv);
    
    for(i=0;i<nv;i++)
        if(indeg[i]==0)
            add(q,i);
            
    int iv;
    iv=0;
    while(!isempty()){
        int u;
        u=delete(q);
        vl[iv++]=u;

        struct node * unode;
        unode=g->adj[u];
        while(unode){
            int v;
            v=unode->v;
            if(!(--indeg[v]))
                add(q,v);
            unode=unode->next;
        }
    }
     
}

int main(){
    Graph  g;
    int n=6;
    g=init(n);

    edge e[8];
    e[0].u=0;e[0].v=2;
    e[1].u=0;e[1].v=3;
    e[2].u=1;e[2].v=3;
    e[3].u=1;e[3].v=4;
    e[4].u=2;e[4].v=3;
    e[5].u=2;e[5].v=5;
    e[6].u=3;e[6].v=5;
    e[7].u=4;e[6].v=5;


    int i;
    for(i=0;i<g->ne;i++)
        insert(g,e[i]);
    topolsort(g);
    for(i=0;i<g->nv;i++)
      printf("%d ",vl[i]);
    printf("\n");
    return 0;
}

时间复杂度分析:有向图的表示采用了邻接链表,所以时间复杂度为:Θ(V+E)。 

拓扑排序

   对一个DAG进行拓扑排序,结果为一个所有顶点构成的线性序列。序列满足:

         对于<u,v>∈E(G),在序列中U出现在V的前面。

在算法导论中,给出的算法是:对DAG进行DFS遍历,计算每个顶点结束的时间,然后每完成一个顶点,将其加入到链表的头部。结果就是链表中的序列。

   因此,对前面的DFS实现,稍加修改就可以了。此外,注意需要对原来的无向图实现修改。

代码:

 

#include<stdio.h>
#include"search.c"
extern int f[MAXV];
int * vq;
void reverse(int * a,int n){
    int i,j;
    for(i=1,j=n-1;i<j;i++,j--){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
void dfsv1(Graph g,int u){
    color[u]=GRAY;
    time++;
    d[u]=time;
    struct node * vnode;
    vnode=g->adj[u];
    while(vnode){
        int vv;
        vv=vnode->v;
        if(color[vv]==WHITE){
            p[vv]=u;
            dfsv1(g,vv);
        }
        vnode=vnode->next;
    }
    color[u]=BLACK;
    time++;
    f[u]=time;
    add(vq,u);
    //printf("%d  ",u);
}
void topolsort(Graph g){
    int i,v;
    
    v=g->nv;
    for(i=0;i<v;i++){
        color[i]=WHITE;
        p[i]=-1;
    }
    vq=initq(NUM);
    time=0;
    for(i=0;i<v;i++)
        if(color[i]==WHITE){
            dfsv1(g,i);
        }
    reverse(vq,v+1);    
}

int main(){
    Graph  g;
    int n=5;
    g=init(n);

    edge e[7];
    e[0].u=0;e[0].v=1;
    e[1].u=0;e[1].v=3;
    e[2].u=1;e[2].v=2;
    e[3].u=1;e[3].v=3;
    e[4].u=1;e[4].v=4;
    e[5].u=4;e[5].v=2;
    e[6].u=3;e[6].v=4;

    int i;
    for(i=0;i<7;i++)
        insert(g,e[i]);
    topolsort(g);
    for(i=1;i<=g->nv;i++)
        printf("%d ",vq[i]);
    printf("\n");
    return 0;
}

找出数组中重复次数最多的元素并打印

    题目:找印。

这道题其实在做汇编实验时,已经做过了。但是当时的思路还是太简单,现在又想了一下,可以先排序,然后遍历。这样如果采用快排,时间复杂度应为:O(nlogn+n)。代码:

 

#include<stdio.h>
#include<stdlib.h>

int int_compare(const void * x1,const void * x2){
	int * a=(int *)x1;
	int * b=(int *)x2;
	return (*a-*b);
}

void findremax(int a[],int n,int *m,int *c){
	int index,count,maxc,i;

	index=0;
	count=1;
	maxc=count;
	//printf("%d\n",(sizeof a )/(sizeof a[0])); Error
	for(i=1;i<n;i++){
		if(a[i]==a[i-1])
			count++;
		else{
			if(count>maxc){
				maxc=count;
				index=i-1;
			}
			count=1;
		}
	}
	if(count>maxc){
		maxc=count;
		index=i-1;
	}

	*m=index;
	*c=maxc;
	
}

int main(){
	int maxindex,c;
	int a[]={1,1,2,2,3,3,3,3,4,5,6,7,7,7,7,7,7};
	int n=(sizeof a)/(sizeof a[0]);
	maxindex=0;
	c=0;
	qsort(a,n,sizeof(a[0]),int_compare);
	findremax(a,n,&maxindex,&c);
	printf("%d appears %d times.\n",a[maxindex],c);

	return 0;
}

总结:1.排序的应用,排序可以用来对相同的元素分类,使他们相邻,从而解决问题。

         2.语言问题:在代码中注释掉的://printf("%d\n",(sizeof a )/(sizeof a[0])); Error。没有注意到:在函数中,a是个指针,而不是数组,分了错误,所以:在32位的机器上:(sizeof a )/(sizeof a[0])=1。

图的搜索

   最近学习图论,课程片中理论。但是,觉得还是实现一下好。就根据书上的写了图的BFS和DFS搜索算法。

1.图的实现,邻接链表。

 

#include<stdlib.h>

typedef struct {int u;int v;} edge;
struct node{int v;struct node * next;}; 
struct graph{int nv;int ne;struct node ** adj;};
typedef struct graph * Graph;

Graph init(int n){
    Graph g=malloc(sizeof *g);// sizeof graph

    g->nv=n;
    g->ne=0;
    g->adj=malloc((sizeof *(g->adj))*n);
    int i;
    for(i=0;i<g->nv;i++)
        g->adj[i]=NULL;
    
    return g;
}

void insert(Graph g,edge e){
    int u,v;

    u=e.u;
    v=e.v;
    
    struct node* unode=malloc(sizeof *unode);
    unode->v=v;
    unode->next=g->adj[u];

    g->adj[u]=unode;

    struct node* vnode=malloc(sizeof *vnode);
    vnode->v=u;
    vnode->next=g->adj[v];

    g->adj[v]=vnode;

    g->ne++;
}

2.队列实现。

 

#include<stdlib.h>

static int maxsize=0;
static int front=0;
static int rear=0;
int * queue;

int * initq(int max){
    maxsize=max+1;
    queue=malloc(sizeof(int)*maxsize);
    front=rear=0;
    return queue;
}

int add(int * q,int v){
    if((rear+1)%maxsize==front)
        return -1;
    rear=(rear+1)%maxsize;
    q[rear]=v;
    return v;
}

int delete(int *q){
    if(front==rear)
        return -1;
    front=(front+1)%maxsize;
    return q[front];
}

int isempty(){
    return (front==rear)?1:0;
}

3.搜索算法。

 

#include<stdlib.h>
#include<stdio.h>
#include"graph.c"
#include"queue.c"
/*bfs,dfs algos. from "introduction to algos".
*/

#define MAXV 1000   
#define BIG  (MAXV+1)
#define NUM 100
int color[MAXV];
int d[MAXV];
int p[MAXV];
int f[MAXV];
enum cl {WHITE,GRAY,BLACK};
int * q;
int time;

void bfs(Graph g,int s){
    int i;

    for(i=0;i<g->ne;i++){
        color[i]=WHITE;
        d[i]=-1;
        p[i]=-1;
    }
    color[s]=GRAY;
    d[s]=0;
    p[s]=-1;

    q=initq(NUM);
    add(q,s);

    while(!isempty()){
        int u;
        u=delete(q);
        printf("%d u \n",u);
        struct node * vnode=g->adj[u];
        while(vnode){
            int v;
            v=vnode->v;
            if(color[v]==WHITE){
                color[v]=GRAY;
                d[v]=d[u]+1;
                p[v]=u;
                add(q,v);
            }
            vnode=vnode->next;
        }
        color[u]=BLACK;
    }
}

void dfsv(Graph g,int u){
    color[u]=GRAY;
    time++;
    d[u]=time;
    struct node * vnode;
    vnode=g->adj[u];
    while(vnode){
        int vv;
        vv=vnode->v;
        if(color[vv]==WHITE){
            p[vv]=u;
            dfsv(g,vv);
        }
        vnode=vnode->next;
    }
    color[u]=BLACK;
    time++;
    f[u]=time;
}

void dfs(Graph g){
    int i,v;

    v=g->nv;
    for(i=0;i<v;i++){
        color[i]=WHITE;
        p[i]=-1;
    }
    time=0;
    for(i=0;i<v;i++){
        if(color[i]==WHITE)
            dfsv(g,i);
    }
}


void printpath(Graph g,int s,int v){
    if(v==s)
        printf("%d ",s);
    else if(p[v]==-1)
        printf("no path from s to v\n");
    else
        {
            printpath(g,s,p[v]);
            printf("%d ",v);
        }
}

int main(){
    Graph  g;
    int n=5;
    g=init(n);

    edge e[7];
    e[0].u=0;e[0].v=1;
    e[1].u=0;e[1].v=3;
    e[2].u=1;e[2].v=2;
    e[3].u=1;e[3].v=3;
    e[4].u=1;e[4].v=4;
    e[5].u=2;e[5].v=4;
    e[6].u=3;e[6].v=4;

    int i;
    for(i=0;i<7;i++)
        insert(g,e[i]);
    bfs(g,0);
    printpath(g,0,4);
    printf("\n");
    dfs(g);
    printpath(g,0,4);
    printf("\n");
    
    return 0;
}

CODE过程中,指针的出错还是有,一定要注意动态分配内存的问题,在这个地方很容易出错。还有就是指向指针的指针问题。对于C来说,指针部分得多练多想呀!不知道,谁有好的理解。




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee