Archive for March, 2007

wow的单机版玩法

Posted by xiaokucha in 山口山 on March 24, 2007

标题党！

其实我是想说我把这个游戏当成单机来玩。首先要庆祝本人今天连续3次单人55级ud mage击杀玛拉顿公主成功。看图说话:

当然大家会有疑问我级别这么低是怎么能活着走到公主面前，更不用提单刷了，其实，由于本人是纯火法，在从瀑布落下(当然有传送杖是前提)，到公主面前的一路中，主要是闪现，冲击波，和冰环的配合使用，这样怪物就一直跟在你的屁股后面走了，等跑到公主面前后，就跳到图中的小石头上面，并同时在石头上面不停走小碎步(当然，我的意思是不能掉下去。。。)，这样就能快速脱离战斗状态了。。。

然后就是单调的绕小石头，火冲杀公主了，目前为止，本人亲身经历过一次无尽黑暗之刃的掉落，被priest以71:2的大比分优势获取，命啊。。。

Leave a comment

knapsack problem

Posted by xiaokucha in Programming on March 14, 2007

From Gossip@caterpillar

Algorithm Gossip: 背包問題（Knapsack Problem）

說明

假設有一個背包的負重最多可達8公斤，而希望在背包中裝入負重範圍內可得之總價物品，假設是水果好了，水果的編號、單價與重量如下所示：

0	李子	4KG	NT$4500
1	蘋果	5KG	NT$5700
2	橘子	2KG	NT$2250
3	草莓	1KG	NT$1100
4	甜瓜	6KG	NT$6700

解法

背包問題是關於最佳化的問題，要解最佳化問題可以使用「動態規劃」（Dynamic programming），從空集合開始，每增加一個元素就先求出該階段的最佳解，直到所有的元素加入至集合中，最後得到的就是最佳解。

以背包問題為例，我們使用兩個陣列value與item，value表示目前的最佳解所得之總價，item表示最後一個放至背包的水果，假設有負重量 1～8的背包8個，並對每個背包求其最佳解。

逐步將水果放入背包中，並求該階段的最佳解：

放入李子

背包負重	1	2	3	4	5	6	7	8
value	０	０	０	4500	4500	4500	4500	9000
item	－	－	－	０	０	０	０	０

放入蘋果

背包負重	1	2	3	4	5	6	7	8
value	０	０	０	4500	5700	5700	5700	9000
item	－	－	－	０	1	1	1	０

放入橘子

背包負重	1	2	3	4	5	6	7	8
value	０	2250	2250	4500	5700	6750	7950	9000
item	－	2	2	０	1	2	2	０

放入草莓

背包負重	1	2	3	4	5	6	7	8
value	1100	2250	3350	4500	5700	6800	7950	9050
item	3	2	3	０	1	3	2	3

放入甜瓜

背包負重	1	2	3	4	5	6	7	8
value	1100	2250	3350	4500	5700	6800	7950	9050
item	3	2	3	０	1	3	2	3

由最後一個表格，可以得知在背包負重8公斤時，最多可以裝入9050元的水果，而最後一個裝入的水果是3號，也就是草莓，裝入了草莓，背包只能再放入7公斤（8-1）的水果，所以必須看背包負重7公斤時的最佳解，最後一個放入的是2號，也就是橘子，現在背包剩下負重量5公斤（7-2），所以看負重5公斤的最佳解，最後放入的是1號，也就是蘋果，此時背包負重量剩下0公斤（5-5），無法再放入水果，所以求出最佳解為放入草莓、橘子與蘋果，而總價為9050元。

實作

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

#define LIMIT 8   // 重量限制 
#define N 5       // 物品種類 
#define MIN 1     // 最小重量 

struct body { 
    char name[20]; 
    int size; 
    int price; 
}; 

typedef struct body object; 

int main(void) { 
    int item[LIMIT+1] = {0}; 
    int value[LIMIT+1] = {0}; 
    int newvalue, i, s, p; 

    object a[] = {{"李子", 4, 4500}, 
                  {"蘋果", 5, 5700}, 
                  {"橘子", 2, 2250}, 
                  {"草莓", 1, 1100}, 
                  {"甜瓜", 6, 6700}}; 

    for(i = 0; i < N; i++) { 
        for(s = a[i].size; s <= LIMIT; s++) { 
            p = s - a[i].size; 
            newvalue = value[p] + a[i].price; 
            if(newvalue > value[s]) {// 找到階段最佳解 
                value[s] = newvalue; 
                item[s] = i; 
            } 
        } 
    } 

    printf("物品t價格n"); 
    for(i = LIMIT; i >= MIN; i = i - a[item[i]].size) { 
        printf("%st%dn", 
                  a[item[i]].name, a[item[i]].price); 
    } 

    printf("合計t%dn", value[LIMIT]); 

    return 0; 
}

Java

class Fruit {
    private String name;
    private int size;
    private int price;
    
    public Fruit(String name, int size, int price) {
        this.name = name;
        this.size = size;
        this.price = price;
    }
    
    public String getName() {
        return name;
    }

    public int getPrice() {
        return price;
    }

    public int getSize() {
        return size;
    }
}

public class Knapsack {
    public static void main(String[] args) {
        final int MAX = 8;
        final int MIN = 1;
        int[] item = new int[MAX+1]; 
        int[] value = new int[MAX+1];  

        Fruit fruits[] = {
                new Fruit("李子", 4, 4500), 
                new Fruit("蘋果", 5, 5700), 
                new Fruit("橘子", 2, 2250), 
                new Fruit("草莓", 1, 1100), 
                new Fruit("甜瓜", 6, 6700)}; 

        for(int i = 0; i < fruits.length; i++) { 
            for(int s = fruits[i].getSize(); s <= MAX; s++) { 
                int p = s - fruits[i].getSize(); 
                int newvalue = value[p] + 
                                   fruits[i].getPrice(); 
                if(newvalue > value[s]) {// 找到階段最佳解 
                    value[s] = newvalue; 
                    item[s] = i; 
                } 
            } 
        } 

        System.out.println("物品t價格"); 
        for(int i = MAX; 
            i >= MIN; 
            i = i - fruits[item[i]].getSize()) { 
            System.out.println(fruits[item[i]].getName()+ 
                    "t" + fruits[item[i]].getPrice()); 
        } 

        System.out.println("合計t" + value[MAX]);  
    }
}

Leave a comment

APC(a perfect circle) Recommended

Posted by xiaokucha in 音乐 on March 13, 2007

老乐队 3张专辑

Mer De Noms

Thirteenth Step

eMotive

风格：
Alternative Metal（另类金属） Alternative Pop/Rock（另类流行/摇滚） Post-Grunge（后垃圾）

介绍：

A Perfect Circle的历史从另一支著名摇滚乐队Tool开始，乐队两个核心Maynard James Keenan，Billy Howerdel在组建A Perfect Circle乐队之前，就分别是Tool乐队主唱和吉他手。其中Billy Howerdel还曾经在Smashing Pumpkins和Nine Inch Nails两支大牌乐队工作过，并且参加过世界著名摇滚乐队Guns N’ Roses(枪炮与玫瑰)专辑《Live Era: ’87-’93》录制工作。Keenan和Howerdel相识是在1992年Tool乐队为老牌摇滚乐队Fishbone做开场演出时候，当时Howerdel还在Fishbone乐队，两人在次演出中很成功配合几首歌，之后他们就走在一起，但是直到离开Tool乐队之后两人才开始真正合作。当他们俩人和贝斯手Paz Lenchantin形成乐队现有基本阵容之后，又招募前Failure乐队和Enemy乐队成员Troy Van Leeuwen作为乐队节奏吉他手，并且吸收前Vandals乐队和Guns N’ Roses乐队后期成员Josh Freese作为鼓手，乐队形成长期稳定。但是虽然五个人在一起排练和创作，但是并没有宣告组成新乐队，直到1999年8月15日他们在洛杉矶一次演唱会之后他们才公布乐队新名字"A Perfect Circle"，并且主由Billy Howerdel担任词曲创作和音乐制作人。

2000年5月23日，乐队发行第一张专辑《Mer de Noms》。后来，出生在阿根廷贝斯手Paz Lenchantin离开乐队(oh,Paz,you are the woman of my life)，接替他是原Marilyn Manson手下贝斯手Jeordie Orsborne Wte(又名Twiggy Ramirez，貌似这位老哥在manson的concert，被manson扔到台下去了，manson够bt。。)。2003年9月16日，乐队第二张专辑《Trteenth Step》正式发行，并且创下乐队历史上单周销量最高(23万1千张)和最高排名(亚军)。2004年11月2日A Perfect Circle发行乐队第三张专辑《感动》"Emotive"。

专辑中除了《Maynard James Keenan》和《Passive》这两首原创歌曲外，其余九首皆为改编歌曲，选曲的范畴跨越朋克、流行、蓝调、民歌等各种不同类型。其中包括约翰·列侬不朽的传世经典单曲《Imagine》，Marvin Gaye的《What’s Going On》Led Zeppelin的《When the Levee Breaks》Joni Mitchell的《Fiddle and the Drum》等等众多的经典老歌。

国籍：美国

ps:个人比较崇拜MJK(Maynard James Keenan)的歌唱功力。。。平静而富有杀伤力，dark silence sad metal，比较喜欢专辑里面的Orestes,Judith,the outsider等。。。

Leave a comment

DataStructure chapter 1

Posted by xiaokucha in Programming on March 13, 2007

Chapter 1 List

List Insert

int ListInsert_L(LinkList &La,int i,ElemType b)
{
    LinkList *p=La;int j=0;
    while(p&&j<i-1)
    {p=p->next;++j;}
    if(!p||j>i-1)
    return 1;
    else
    {
    s= new LNode;//s=(LinkList)malloc(sizeof(LNode));
    s->data=b;
    s->next=p->next;
    p->next=s;
    return 0;
    }
}

List Delete

int ListDelete_L(LinkList &La,int i,ElemType &b)
{
    LinkList *p=La;int j=0; LinkList *q;
    while(p&&j<i-1)
    {p=p->next;++j;}
    if(!(p->next)||j>i-1)
    return 1;
    else
    {
    q=p->next;
    p->next=q->next;
    b=q->data;
    delete q;
    return 0:
    }
}

List Create

Void CreatList_L(LinkList &a,ElemType a[],int i)
{
    la=new LNode;la->next=NULL;
    for(i=n;i>=1;i–)
    {
    p=new LNode;
    p->data=a[i];
    p->next=la->next;
    la->next=p;
    }
}

List Intersect(with or without old space,both sequential list)

Void Intersect(LinkList &a,LinkList &b) //use given
{
ap=a->next;bp=b->next;tp=a;
while(ap)
{
    if(!bp||ap->data<bp->data)
    {
    tp->next=ap->next;
    delete ap;
    ap=tp->next;}
    else if(ap->data=bp->data)
    {
    tp=ap;
    ap=ap->next;
    bp=bp->next;
    }
    else bp=bp->next;
}
}

Void Intersect(LinkList &c,LinkList a,LinkList b) //copy node
{
    c= new LNode;
    ap=a->next;bp=b->next;cp=c;
    while(ap&&bp)
    {
    if(ap->data=bp->data)
    {
    tp=new LNode;
    tp->data=ap->data;
    cp->next=tp;cp=tp;
    ap=ap->next;
    bp=bp->next;
    }
    else if(ap->data<bp->data)
    ap=ap->data;
    else
    bp=bp->data;
    }
    cp->next=NULL;
}

List Complement

Void Complement(LinkList &a,LinkList &b) //use given
{
     ap=a->next;bp=b->next;tp=a;
     while(ap&&bp)
     {
     if(!bp||ap->data<bp->data)
     {
     ap=ap->next;
     tp=tp->next;
     }
     else if(ap->data==bp->data)
     {
     tp->next=ap->next;
     delete ap;
     ap=tp->next;
     }
     else
     bp=bp->next;
     }
}

Void Complement(LinkList &c,LinkList a,LinkList b)   //copy node
{
     c=new LNode;
     ap=a->next;
     bp=b->next;
     cp=c;
     while(ap)
     {
     if(!bp)
     {
     tp=new LNode;
     cp->next=tp;cp=tp;cp->data=ap->data;ap=ap->next;
     }
     else if(ap->data<bp->data){
     tp=new LNode;cp->next=tp;cp=tp;cp->data=ap->data;ap=ap->next;
     }
     else if(ap->data==bp->data){
     ap=ap->next;bp=bp->next;
     }
     else bp=bp->next;
     }
     cp->next=NULL;
}

List Union

Void Union(LinkList &a,LinkList &b)   //use given
{
     ap=a->next;bp=b->next;tp=a;
     while(ap&&bp)
     {
     if(ap->data<bp->data)
     {tp->next=ap;tp=ap;ap=ap->next;}
     else if(ap->data>bp->data)
     {tp->next=bp;tp=bp;bp=bp->next;}
     else{
     tp->next=ap;tp=bp;bp=bp->next;
     delete tp;
     tp=ap;ap=ap->next;}
     }
     if(ap)tp->next=ap;
     else tp->next=bp;
     delete b;
}

void Union(LinkList &c,LinkList a,LinkList b)   //copy node
{
     c=new LNode;
     ap=a->next;bp=b->next;cp=c;
     while(ap||bp)
     {
     tp=new LNode;
     cp->next=tp;
     cp=tp;
     if(!ap)
     {cp->data=bp->data;bp=bp->next;}
     else if(!bp)
     {cp->data=ap->data;ap=ap->next;}
     else if(ap->data==bp->data)
     {cp->data=ap->data;ap=ap->next;bp=bp->next;}
     else if(ap->data<bp->data)
     {cp->data=ap->data;ap=ap->data;}
     else
     {cp->data=bp->data;bp=bp->data;}
     cp->next=NULL;
}

1 Comment

根据preorder和inorder显示tree

Posted by xiaokucha in Programming on March 1, 2007

没事写着玩，练手。。。

ps:没有注释，数组有限制，内存溢出，等等等，很多问题，

何必呢，搞研究的不是要讲究"理想状态下"么？

sample input:

please input the pre sequence:abcdefg
the input length is:7
plz input the in sequence:cbedafg

sample output:

4
0 0 7 4 1 0 0
1 0 4 4 2 7 1
2 0 1 4 3 4 1
3 0 0 4 4 2 1
3 1 0 4 4 2 2
3 2 2 4 3 4 2
4 2 1 4 4 6 1
5 2 0 4 5 5 1
5 3 0 4 5 5 2
5 4 0 4 4 6 2
5 5 2 4 2 7 2
6 5 0 4 3 10 1
6 6 1 4 3 10 2
7 6 0 4 4 12 1
7 7 0 4 4 12 2
       a
    b     f
c   d     g
     e

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

int pp,ip,n;
char treepre[10],treein[10];
char output[50][50];

int
getlv(char *s,char *t,int a,int b,int len){
    //printf("%d %d %dn",a,b,len);
    int i=1,n,m;

    if(len==0)
    return 0;
    else{
        while((s[a]!=t[b+i-1])&&i<len)
        i++;
        n=1+getlv(s,t,a+1,b,i-1);
        m=1+getlv(s,t,a+i,b+i,len-i);
        return (n>m)?n:m;
    }
     }
void prein(char *s,char *t,int a,int b,int len,int lv,int lvn,int pos,int lorr)
{
     printf("%d %d %d %d %d %d %dn",a,b,len,lv,lvn,pos,lorr);
     if(lorr==0){

     pos=(pow(2,lv)-1)/2;
     //printf("%dn",pos);
     }

     else if(lorr==1)
     pos=pos-(lv-lvn+1);
     else if(lorr==2)
     pos=pos+(lv-lvn+1);
     int i=1;
     if(len!=0)
     {
          while((s[a]!=t[b+i-1])&&i<len)
          i++;
          output[lvn-1][pos]=s[a];
          lvn++;
          prein(s,t,a+1,b,i-1,lv,lvn,pos,1);
          prein(s,t,a+i,b+i,len-i,lv,lvn,pos,2);
          }
}

//void prein(
int main()
{
int n,m,lv=1,len;
for(n=0;n<50;n++)
for(m=0;m<50;m++)
output[n][m]=’ ‘;

pp=ip=0;
printf("please input the pre sequence:");
scanf("%s",treepre);
// printf("%s",sf);
len=n=strlen(treepre);
printf("the input length is:%d",n);
printf("nplz input the in sequence:");
scanf("%s",treein);
m=strlen(treein);
if(m!=n){printf("error: pre not equal to in");exit(0);}
//while((n=n/2)!=0)
//lv++;
lv=getlv(treepre,treein,0,0,len);
printf("%dn",lv);
prein(treepre,treein,0,0,len,lv,1,0,0);

for(n=0;n<50;n++){
for(m=0;m<50;m++){
printf("%c",output[n][m]);}
printf("n");}
// printf("%s",sm);
system("PAUSE");
return 0;
}

Leave a comment

calculator

Posted by xiaokucha in Programming on March 1, 2007

给刘洋写的calculator，有点垃圾，虽然支持浮点数但是还没有加"%" "^"和三角函数的运算，算符优先比较也就是prec()弄得我头大，以前的东西都忘了，tnnd，调试半天。。。谁给我写个好一点的。。。我拿来用

抛砖引玉，看客给提点意见。。

sample input:

25.0/2+(34+2)*3/3#

output:

48.5

code:

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

#define MAXOP 100
#define NUMBER 0
#define BUFSIZE 100
#define MAXVAL 100

int sp_nd=0;
int sp_op=0;
char buf[BUFSIZE];
int bufp=0;
double OPND[MAXVAL];
char OPTR[MAXOP];

void pushnd(double f)
{
if(sp_nd<MAXVAL)
  OPND[sp_nd++]=f;
else
  printf("error: nd stack full,can’t push %gn",f);
}
void pushop(char w)
{
if(sp_op<MAXOP)
  OPTR[sp_op++]=w;
else
  printf("error: op stack full,can’t push %cn",w);
}

double popnd(void)
{
double a;
    if(sp_nd>0)
    {a=OPND[–sp_nd];
    OPND[sp_nd]=”;
  return a;}
else{
  printf("error: nd stack emptyn");
return 0;
}
}
char popop(void)
{
    char a;
    if(sp_op>0){
    a=OPTR[–sp_op];
    OPTR[sp_op]=”;
  return a;}
else{
  printf("error: op stack emptyn");
  return 0;
}
}

int getch(void)
{
return (bufp>0)?buf[–bufp]:getchar();
}

void ungetch(int c)
{
if(bufp>=BUFSIZE)
printf("ungetch:too many charactersn");
else
buf[bufp++]=c;
}

/*double atof(char s[])
{
double val,power;
int exp,i,sign;
for (i=0;isspace(s[i]);i++)
  ;
sign = (s[i]==’-‘)?-1:1;
if(s[i]==’+’||s[i]==’-‘)
  i++;
for(val=0.0;isdigit(s[i]);i++)
  val=10.0*val+(s[i]-‘0’);
if(s[i]==’.’)
  i++;
for(power=1.0;isdigit(s[i]);i++)
{
  val=10.0*val+(s[i]-‘0’);
  power*=10.0;
}
val=sign*val/power;
if(s[i]==’e’||s[i]==’E’){
  sign=(s[++i]==’-‘)?-1:1;
  if(s[i]==’+’||s[i]==’-‘)
   i++;
  for(exp=0;isdigit(s[i]);i++)
   exp=10*exp+(s[i]-‘0’);
     if(sign==1)
   while(exp–>0)
    val*=10;
   else
    while(exp–>0)
     val/=10;
    }
return val;
}*/

int
getop(char s[])
{
int i,c;
while((s[0]=c=getch())==’ ‘|| c==’t’)
  ;
s[1]=”;
i=0;
if(!isdigit(c)&&c!=’.’&&c!=’-‘)
  return c;
if(c==’-‘)return ‘-‘;
//c==getch();
  /*if(c==’-‘){
        if(isdigit(c==getch())||c==’.’)
   s[++i]=c;
  else{
   if(c!=EOF)
    ungetch(c);
   return ‘-‘;
  }*/
if(isdigit(c))
  while (isdigit(s[++i]= c =getch()))
   ;
    if(c==’.’)
  while(isdigit(s[++i]=c=getch()))
   ;
  s[i]=”;
  if(c != EOF)
   ungetch(c);
//  printf("%sn",s);
  return NUMBER;
}

double operate(double a,char theta,double b){
double result;
printf("%cn",theta);
switch(theta){
case ‘+’:result=a+b;break;
case ‘-‘:result=a-b;break;
case ‘*’:result=a*b;break;
case ‘/’:result=a/b;break;
default:
printf("op resolving error: %cn",theta);
}
printf("operate result:%gn",result);
return result;
}

char Prec(char a,char b){
printf("%c,%cn",a,b);
printf("%dn",sp_op);
    if(a==’)’&&b!='(‘)
return ‘<‘;
if(a=='(‘)
return ‘>’;
if((a==’)’)&&(b=='(‘))
return ‘=’;
    if(a==’#’)
    return ‘<‘;
    if(b==’#’)
    return ‘>’;
    if((a==’+’)||(a==’-‘))
{
    if(b=='(‘)
    return ‘>’;
else
    return ‘<‘;

    }
if((a==’*’)||(a==’/’))
{
  if(b==’*’||b==’/’||b=='(‘)
   return ‘<‘;
  else if(b==’+’||b==’-‘||b==’)’)
   return ‘>’;
}

}

int
main()
{
double a,b;
char x,theta;
    int c,d;
int type=0;
char w[MAXOP];
memset(w,0,sizeof(char));
pushop(‘#’);
type=getop(w);
while(!((type==’#’)&&OPTR[sp_op-1]==’#’))
   if(!type)
   {printf("%dn",type);pushnd(atof(w));
            c=d=0;
            while(OPND[c]!=0)
            printf("%gn",OPND[c++]);
            while(OPTR[d]!=”)
            printf("%cn",OPTR[d++]);
            system("pause");
            type=getop(w);
            printf("%dn",type);printf("get op: %sn",w);
            system("pause");}
   else {
                 printf("%cn",Prec(type,OPTR[sp_op-1]));
            switch (Prec(type,OPTR[sp_op-1])){
    case ‘>’: pushop(type);type=getop(w);printf("get op: %sn",w);break;
    case ‘=’: x=popop();type=getop(w);printf("get op: %sn",w);break;
    case ‘<‘: theta = popop();
     b=popnd();a=popnd();
     pushnd(operate(a,theta,b));
     break;
        }
        }
x=popop();
printf("nresult is %g",popnd());
system("pause");
    return 0;
}

2 Comments

Page cannot be found

Archive for March, 2007

wow的单机版玩法

knapsack problem

From Gossip@caterpillar

Algorithm Gossip: 背包問題（Knapsack Problem）

說明

解法

實作

APC(a perfect circle) Recommended

DataStructure chapter 1

根据preorder和inorder显示tree

calculator

Recent Posts

Archives

Categories

Meta