複雜度筆記

○(n)   :  f(n) <= c*g(n)           bigO最多會執行幾次

       

Ω(n)   :  f(n) >= c*g(n)           Omega最少會執行幾次

Θ(n)   :  c1*g(n)<=f(n) <= c2*g(n)  theta執行次數會被夾在範圍內

Ex:

     3n+2
          可知bigO是○(n)，知道g(n)=n，代表意思 3n+2<=c*n其中C=4且n>=2。

EX:

A程式的時間複雜度是T1(N)

B程式的時間複雜度是T2(N)

                 A做完接著做B，整體的BIGO=MAX( T1(N) , T2(N) )

         A內呼叫B做遞迴，整體的BIGO=T1(N)*T2(N)

常用的大小表：C < LOGN < LOG^2 N < N < NLOGN < N^2 < N^3 <2^N

UVA 10107 C++

#include<iostream>
#include<stdio.h>
using namespace std;
long long data[10000];
void print(long long);
int main()
{
long long X,count=0,trace;
while(cin>>X)
{
if(count==0)
{
data[0]=X;
count++;
print(count);
}
else
{
trace=count;
if(X>=data[trace-1])
{
data[trace]=X;
count++;
print(count);
}
else
{
while(X<=data[trace-1])
{
data[trace]=data[trace-1];
trace--;
}
data[trace]=X;
count++;
print(count);
}

}
}
return 0;
}
void print(long long tmp)
{
if( (tmp%2)!=0)
cout<<data[tmp/2]<<endl;
else
cout<<(data[tmp/2]+data[tmp/2-1])/2<<endl;
}

UVA 10077 C++

#include<iostream>
#include<string>
using namespace std;
int main()
{
START:
string path="";
int m,n;
while(cin>>m,cin>>n)
{
if( m==1 && n==1)
break;
int uppertop=1,upperdown=0,lowertop=0,lowerdown=1;
int midtop,middown;
double mid,mn;
while(true)
{
midtop=uppertop+lowertop;
middown=upperdown+lowerdown;
mid=midtop*1.0/middown;
mn=m*1.0/n;
if(midtop==m && middown==n)
{
cout<<path<<endl;
goto START;
}
else if(mid>=mn)
{
uppertop=midtop;
upperdown=middown;
path=path+'L';
}
else
{
lowertop=midtop;
lowerdown=middown;
path=path+'R';
}
}

}
return 0;
}

LIST變形 C++

假設現在有兩個LIST(圖片one two)，我可以選擇要動哪一個list(選擇動哪張圖片移動到新的位置)，如果沒動到的那張圖片，希望也要出一個空間，存的XY就是原本的位置。
此時希望可以有恢復的功能(linking list的返回鍵left)，也希望可以下一步(linking list的right)

#include<iostream>
using namespace std;
struct list
{
list* left;
int x;
int y;
list* right;
};
int main()
{
list one;
list two;
cout<<"請輸入第1張圖的X和Y位置"<<endl;
cin>>one.x;
cin>>one.y;
one.left=NULL;
one.right=new list;
cout<<"請輸入第2張圖的X和Y位置"<<endl;
cin>>two.x;
cin>>two.y;
two.left=NULL;
two.right=new list;
list* pre;
list* current;
list* next;
int choice,count=0;
while(true)
{
cout<<"請輸入要更動哪一個圖片one or two"<<endl;
cin>>choice;
if(choice==1)
{
current=one.right; //initial 1
pre=&one;
for(int i=0;i<count;i++) //find new one
{
pre=current;
next=current->right;
current=next;
}
cout<<"請輸入第1張圖新的X和Y位置"<<endl;
cin>>current->x; //new
cin>>current->y;
current->left=pre;
current->right=new list;
current=two.right; //initial 2
pre=&two;
for(int j=0;j<count;j++) //find new two
{
pre=current;
next=current->right;
current=next;
}
current->left=pre;
current->right=new list;
current->x=current->left->x; //copy two data
current->y=current->left->y;
count++;
}
else if(choice==2)
{
current=two.right; //initial 2
pre=&two;
for(int j=0;j<count;j++) //find new two
{
pre=current;
next=current->right;
current=next;
}
cout<<"請輸入第2張圖新的X和Y位置"<<endl;
cin>>current->x; //new
cin>>current->y;
current->left=pre;
current->right=new list;
current=one.right; //initial 1
pre=&one;
for(int i=0;i<count;i++) //find new one
{
pre=current;
next=current->right;
current=next;
}
current->left=pre;
current->right=new list;
current->x=current->left->x; //copy one data
current->y=current->left->y;
count++;
}
else
break;
}

/*trace 使用
current=&one;
for(int k=0;k<=count;k++)
{
cout<<current->x<<"   "<<current->y<<endl;
next=current->right;
current=next;
}
*/
return 0;
}

當然此程式可以看出choice==one or two 內有很多地方是做一樣的事情，應該可以額外寫個function去genrealize，但是由於懶惰，就不想優化了....

雙向linking list C++

先按1 在案2

#include<iostream>

using namespace std;

struct typeA

{

typeA *pre;

int x;

int y;

typeA *next;

};

int main()

{

typeA *left;

typeA data; //先弄第一個出來

data.pre=NULL;

data.x=10;

data.y=10;

data.next=new typeA;

left=&data; //讓left記路目前位置

typeA *right; //宣告一個right出來

right=data.next; //指到data的下一個

right->x=20;

right->y=20;

right->pre=left;

typeA *now;

now=&data;

while(true) //測試先按1 在案2

{ int n;

cin>>n;

if(n==1)

{

now=now->next;

cout<<now->x<<endl;

}

if(n==2)

{

now=now->pre;

cout<<now->x<<endl;

}

}

return 0;

}

NCNU LISP HW9

: finding the n-th leaf of a tree

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))
(define nil '())

(define x (list 1 (list 2 (list 3 4)) 5))

(define (tree-ref L n)
(do-tree-ref L n 1)
)
(define (do-tree-ref L n flag)
(cond ((= flag 1) (do-tree-ref (enumerate-tree L) n 0))
     ((= n 0) (car L))
     (else (do-tree-ref (cdr L) (- n 1) 0))
)
)

LISP NCNU HW手寫exercise2.1

(define (make-rat n d)
(cond ( (and (< n 0) (< d 0)) (let ((g (gcd n d))) (cons (/ (- n) g) (/ (- d) g))))
     ( (and (> n 0) (< d 0)) (let ((g (gcd n d))) (cons (/ (- n) g) (/ (- d) g))))
     (else (let ((g (gcd n d))) (cons (/ n g) (/ d g))))
)
)
(define (gcd a b)
  (if (= b 0)
      (if (< a 0) (- a)
    a)
      (gcd b (remainder a b))))

NCNU LISP HW7

(define (iterative-improve ok? do)
(define (iim guess)
(if (ok? guess) guess
                    (iim (do guess))
)
)
iim)
(define (square x)
(* x x))
(define (average x y)
    (/ (+ x y) 2))

(define (sqrt x)
   ((iterative-improve (lambda (guess)
                        (< (abs (- (square guess) x)) 0.001))
                       (lambda (guess)
                          (average guess (/ x guess))))
   1.0)
)

(define (fixed-point f guess)
   ((iterative-improve (lambda (guess)
                          (< (abs (- (f guess) guess)) 0.00001))
                       (lambda (guess)
                          (f guess)))
    guess)
)

NCNU LISP HW8

exercise 8: Combining three numbers with exponentiation and multiplication

• Refer to exercise 2.5 but the pair is replaced with a triple. That is, the interface functions are :
  (combine a b c), (first x), (second x), (third x)

(define (combine a b c)

  (do-combine a b c 1)

) 

(define (do-combine a b c num)

(if (= a 0)

(if (= b 0)

(if (= c 0) num

           (do-combine a b (- c 1) (* 5 num))

)

   (do-combine a (- b 1) c (* 4 num))

)

   (do-combine (- a 1) b c (* 3 num))

  )

)

(define (first x)

(common x 3)

)

(define (second x)

(common x 4)

)

(define (third x)

(common x 5)

)

(define (common n f)

(define (do-common x num)

(if (> (remainder x f) 0)

   num

    (do-common (/ x f) (+ num 1))

)

)

 (do-common n 0)

)

NCNU LISP HW6

computing the continued fractions

• Refer to exercise 1.37.
• Both versions of linear recusive and linear iterative are required.
• Deadline: 2013 Apr 27 00:05 am

(define (cont-frac-iterative N D K)
        (do-cont-frac-iterative N D K 0)
)
(define (do-cont-frac-iterative N D K result)
        (if (= k 0) result
                    (do-cont-frac-iterative N D (- k 1) (/ (N K) (+ (D K)
result) ))
        )
)
(define (cont-frac-recursive N D K)
        (do-cont-frac-recursive N D K 1)
)

(define (do-cont-frac-recursive N D K counter)
        (if (= k 1) (/ (N counter) (D counter))
                    (/ (N counter) (+ (D counter) (do-cont-frac-recursive N
D (- k 1) (+ counter 1))))
        )
)

UVA 106 C++

#include<iostream>
using namespace std;
int gcd(int,int);
int main()
{
int n;
while(cin>>n)
{
bool *stored=new bool[n+1];
int count=0,second_count=0;
int f,s,t;
for(int a=1;a<=1000;a++)
for(int b=1;b<=a;b++)
{
if(gcd(a,b)!=1)
continue;
if((a-b)%2==0)
continue;
t=a*a+b*b;
if(t>n)
break;
count++;
f=a*a-b*b,s=2*a*b;
for (int i=1; t*i<=n; i++ )
stored[i*f]=stored[i*s]=stored[i*t]=1;
}
for(int j=1;j<=n;j++)
if(stored[j]==1)
second_count++;
cout<<count<<" "<<n-second_count<<endl;
}
return 0;
}
int gcd(int m,int n)
{
int Remainder;
while(Remainder=m%n)
{
m=n;
n=Remainder;
}
return n;
}

NCNU LISP HW5

omputing the continued fractions

• Refer to exercise 1.37.
• Both versions of linear recusive and linear iterative are required.

/////////////////////////////////////////////////////////////////////////////////

(define (cont-frac-iterative N D K)

(do-cont-frac-iterative N D K 0)

)

(define (do-cont-frac-iterative N D K result)

(if (= k 0) result

           (do-cont-frac-iterative N D (- k 1) (/ (N K) (+ (D K) result) ))

)

)

(define (cont-frac-recursive N D K)

(do-cont-frac-recursive N D K 1)

)

(define (do-cont-frac-recursive N D K counter)

(if (= k 1) (/ (N counter) (D counter))

   (/ (N counter) (+ (D counter) (do-cont-frac-recursive N D (- k 1) (+ counter 1))))    

)

)

NCNU LISP HW5

For 1.31, you have to write the `term' function.
That is (the fucntion will return a float.)

              (term 1) --> 2/3 = 0.6666666...
              (term 2) --> 4/3 = 1.3333333...
              (term 3) --> 4/5 = 0.8
              

For 1.32, you have to write the `accumulate'. It can be done either in the way of linear recusive or linear iterative. Only one version is required.

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

(define (term x)
(do-term x 2 3)
)
(define (do-term x numerator denominator)
   (cond ((= x 1)   (/ (* numerator 1.0) denominator))
((even? x) (do-term (- x 1) (+ numerator 2) denominator))
(else      (do-term (- x 1) numerator (+ denominator 2)))
   )
)
(define (even? n)
        (= (remainder n 2) 0)
)



(define (accumulate combiner null-value term1 a next b)
(if (> a b) null-value
                    (combiner (term1 a) (accumulate combiner null-value term1 (next a) next b))
)
)

(define (product term2 a next b)
(accumulate * 1 term2 a next b)
)
(define (sum term3 a next b)
(accumulate + 0 term3 a next b)
)
(define (inc x)
(+ x 1)
)
(define (identify x)
x
)

UNIX IN NCNU filtering numbers (python)

與作業七相同, 但改用 python 來作.

#!/usr/local/bin/python
import sys
import string
lower=string.atoi(sys.argv[1]);
upper=string.atoi(sys.argv[2]);
count=0;
line=sys.stdin.readlines();
long=len(line);
single=[]
for i in range(0,long):
  line[i]=line[i][:-1];
  single=line[i].split();
  long2=len(single)
  for j in range(0,long2):
    single[j]=string.atoi(single[j]);
    if (single[j]>=lower):
      if (single[j]<=upper):
        if (count<5):
          print single[j],;
          count=count+1;
        else:
          print single[j];
          count=0;        

UNIX IN NCNU filtering numbers (shell script)

寫一 sh 的 script file, 例如為 ex7.sh
從參數讀進 lower bound 與 upper bound,
從 stdin 讀進 numbers.
把介於 lower bound 與 upper bound 的數以六個一列印出.
如下例所示.

$ cat N 
3 4 5 6 7 8 9 10
9 88 23 
121
98 78 34 288
345 909
3 2 1
$ ./ex7.sh 40 50 < N
$ ./ex7.sh 4 50 < N
     4      5      6      7      8      9 
    10      9     23     34 
$ ./ex7.sh 1 10 < N
     3      4      5      6      7      8 
     9     10      9      3      2      1 
$ ./ex7.sh 11 100 < N
    88     23     98     78     34 

///////////////////////////////////////////////////////////////////////

#!/bin/bash
count=0
lower=$1
upper=$2
while read line;do
  for number in $line;do
        if [ "$number" -le "$upper" ];then
                 if [ "$lower" -le "$number" ];then
                        if [ "$count" -lt 5 ];then
                                echo -n "$number "
                                count=`expr $count + 1`
                        else
                                echo $number
                                count=0
                        fi
                fi
        fi
  done
done
if [ "$count" -gt 0 ];then
echo
fi

UNIX IN NCNU writing sh script

寫一 sh 的 script file, 例如為 ex6.sh. 其執行結果與作業五類似. 如下例所示.

$ ./ex6.sh 
klim: 29747 29957 29958
root: 0 1 2 3 52 62 137 160 174 184 185 196 210 215 223 248 260 262 263 292 298 301 310 316 317 319 321 324 325 326 327 341 1755 12321 29745
smmsp: 236 12322
daemon: 176
$ ps -e -o user,pid | ./ex5.awk 
klim: 29747 29962 29963
smmsp: 236 12322
daemon: 176
root: 0 1 2 3 52 62 137 160 174 184 185 196 210 215 223 248 260 262 263 292 298 301 310 316 317 319 321 324 325 326 327 341 1755 12321 29745

///////////////////////////////////////////////////////////////////////

#!/bin/bash
index=-1
tmp=" "
ps -e -o user,pid | sed '1d' | sort >>doc.txt
while read user pid;do
        #printf "%s : %s\n" $user $pid
        if [ "$tmp" = "$user" ];then
                        number[$index]=${number[$index]}' '$pid
                        name[$index]=$user':'
        else
                index=`expr $index + 1`
                number[$index]=${number[$index]}' '$pid
                name[$index]=$user':'
        fi
        tmp=$user
done<doc.txt

for((i=0;i<=index;i=i+1))
do
        echo  "${name[$i]}${number[$i]}"
done
rm doc.txt

UNIX IN NCNU writing awk script

將 ps -ef 的輸出的

• 第一行砍掉
• 將同一 user 的 pid 順序印出

$ ps -ef | ./ex5.awk 
klim: 27048 27141 27142
smmsp: 236 12322
daemon: 176
root: 0 1 2 3 52 62 137 160 174 184 185 196 210 215 223 248 260 262 263 292 298 301 310 316 317 319 321 324 325 326 327 341 1755 12321 27046

///////////////////////////////////////////////////////////////////////

這邊耍蠢了，不知道為啥我CALL內建的sort竟然不能用，於是我就自己寫了一個bubble sort來用

其實這邊的for*2可以改成內建的sort使用

#!/bin/awk -f
/^UID/{next}
!/UID/{
name=""
name=$1
user[name]=name
number[name]=number[name]" "$2
}
END{
  answer=""
  for(j in number)
  {
     n=split(number[j],tmp," ")
    for(change1=1;change1<=n;change1++)
    {
      for (change2=1;change2<=n-1;change2++)
      {
        if(tmp[change2]>tmp[change2+1])
        {
         temp=tmp[change2];
         tmp[change2]=tmp[change2+1];
         tmp[change2+1]=temp;
        }
      }
    }
    for(i=1;i<=n;i++)
    {
      if(i>1)
      after[j]=after[j]" "tmp[i]
      else
      after[j]=tmp[i]
    }
  }
  for( i in user )
     printf "%s : %s\n",i,after[i]

UNIX IN NCNU writing sed script

作業四: writing sed script
將適當的 sed 的 commands 寫成一個 script file, 例如為 ex4.sed,
如底下方式執行, 將 ps -ef 的輸出的

• 第一行砍掉
• user 為 root 的砍掉
• 其餘的只顯示前二個欄位, 中間空一格
  $ ps -ef | sed -f ex4.sed

  s9832100 18776
  daemon 176
  smmsp 236
  s9832100 18749
  klim 18818
  klim 18817
  smmsp 12322
  klim 18641

  ///////////////////////////////////////////////////////////////////

  1d
  /root/d
  s/\ \ [01] [0-9a-zA-Z\:\-\/\ *].*$//g

NCNU LISP HW4

(define (expmod base exp m)
(iterative-expmod base 1 exp m)
)
(define (iterative-expmod base1 base2 exp m)
(cond ((= exp 0) base2)
     ((even? exp) (iterative-expmod (mod (square base1) m) base2 (/ exp 2) m)  )
     (else        (iterative-expmod base1 (mod (* base1 base2) m) (- exp 1) m)  )
)
)
(define (mod a b)
(remainder a b)
)
(define (even? n)
(= (remainder n 2) 0)
)
(define (square x)
(* x x)
)

c++ UVA100

#include<iostream>
using namespace std;
int main()
{
unsigned long long i,j,length,tmp,max;
while(cin>>i>>j)
{
max=0;
cout<<i<<" "<<j<<" ";
if(i>j)                                               //很重要，我沒直接想到
{
unsigned long long change;
change=i;
i=j;
j=change;
}
for(unsigned long long k=i;k<=j;k++)
{
length=0;
tmp=k;
while(tmp!=1)
{
length++;
if(tmp%2==1)
tmp=3*tmp+1;
else
tmp=tmp/2;
}
if(tmp==1)
length++;
if(length>max)
max=length;
}
cout<<max<<endl;
}

return 0;
}

c++ Uva 11450

問題連結：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2445

DP問題=>背包變型


#include<iostream>
using namespace std;
int main()
{
int n,m,c,k,min,sum,max;
int table[20][21];
int T[21][201];
cin>>n;
for(int i=1;i<=n;i++)
{
sum=0;
cin>>m;
cin>>c;
for(int j=0;j<=c-1;j++)
{
min=99999;
cin>>table[j][0];
k=1;
while(k<=table[j][0])
{
cin>>table[j][k];
if(table[j][k]<=min)
min=table[j][k];
k++;
}
sum=sum+min;
}
if(sum>m)
{
cout<<"no solution"<<endl;
continue;
}
else
{
for(int b=0;b<=c;b++)
for(int a=0;a<=m;a++)
T[b][a]=0;
for(int q=1;q<=c;q++)
for(int p=1;p<=m;p++)
{
for(int o=1;o<=table[q-1][0];o++)
{
if(p>=table[q-1][o])
{
if((q==1) && (T[q-1][p-table[q-1][o]]+table[q-1][o])>=T[q][p])
T[q][p]=T[q-1][p-table[q-1][o]]+table[q-1][o];
else
if((T[q-1][p-table[q-1][o]]+table[q-1][o])>=T[q][p] && (T[q-1][p-table[q-1][o]])>0)
T[q][p]=T[q-1][p-table[q-1][o]]+table[q-1][o];
}
}


}
cout<<T[c][m]<<endl;
}
}
return 0;
}

c++ 大數加法

#include<iostream>

#include<string>

#include<vector>

using namespace std;

int main()

{

 vector<int>bit1,bit2;

 string input1,input2;

 int length1,length2,tmp;

 bool flag=0,next=0;   //預先判斷要不要進位；下一次進算時把進位的數字加上去

 cout<<"輸入第一個數字"<<endl;

 cin>>input1;

 cout<<"輸入第二個數字"<<endl;

 cin>>input2;

 for(int i=0;i<=input1.length()-1;i++)  //把string的char一個一個存成int

  bit1.push_back(input1[i]-'0');

 for(int j=0;j<=input2.length()-1;j++)

  bit2.push_back(input2[j]-'0');

 length1=input1.length()-1;

 length2=input2.length()-1;

 if(length1>=length2)      //當第1個字串大於第2個字串時

  while(1)

  {

   if(length2==-1)

   {

    bit1[length1]=(bit1[length1]+next)%10;

    if(next==1)

    {

     bit1.push_back(next);

     for(int k=0;k<=input1.length();k++)

     {

      tmp=bit1[k];

      bit1[k]=bit1[input1.length()];

      bit1[input1.length()]=tmp;

     }

    }

    break;

   }

   if((bit1[length1]+bit2[length2])>=10)

    flag=1;

   bit1[length1]=(bit1[length1]+bit2[length2])%10+next;

   next=flag;

   flag=0;

   length1--;

   length2--;

  }

 else          //當第2個字串大於第1個字串時

  while(1)

  {

   if(length1==-1)

   {

    bit2[length2]=(bit2[length2]+next)%10;

    if(next==1)

    {

     bit2.push_back(next);

     for(int k=0;k<=input2.length();k++)

     {

      tmp=bit2[k];

      bit2[k]=bit2[input2.length()];

      bit2[input2.length()]=tmp;

     }

    }

    break;

   }

   if((bit1[length1]+bit2[length2])>=10)

    flag=1;

   bit2[length2]=(bit1[length1]+bit2[length2])%10+next;

   next=flag;

   flag=0;

   length1--;

   length2--;

  }

  if(input1.length() >= input2.length())

  {

   if(next==1)

    for(int i=0;i<=input1.length();i++)

     cout<<bit1[i];

   else

    for(int i=0;i<=input1.length()-1;i++)

     cout<<bit1[i];

  }

  else

  {

   if(next==1)

    for(int i=0;i<=input1.length();i++)

     cout<<bit1[i];

   else

    for(int i=0;i<=input1.length()-1;i++)

     cout<<bit1[i];

  }

  cout<<endl;

 return 0;

}

c++ 簡易linking list

#include<iostream>

using namespace std;

struct link

{

 int number;

 link *next;

};

int main()

{

 int times;

 link first;

 link *current;

 cout<<"輸入要多大的int空間：";

 cin>>times;

 cout<<"請輸入數值"<<endl;

 cin>>first.number;

 first.next=new link;

 current=first.next;

 for(int i=1;i<times;i++)

 {

 cin>>current->number;

 current->next=new link;

 current=current->next;

 }

 current=&first;

 for(int j=0;j<times;j++)

 {

  cout<<"第"<<j+1<<"次輸入的數值"<<current->number<<endl;

  current=current->next;

 }

 return 0;

}

c++ 一串string type的數字，以逗號分開存成int的type

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
         vector<int>i_num;
         string str="10,20,30,40,50";
         string num="";
         int location=-1;
         for(int i=0;i<=str.length()-1;i++)
         {
                  if(str[i]==',')
                  {
                           for(int j=location+1;j<=i-1;j++)
                             num=num+str[j];
         i_num.push_back(atoi(num.c_str()));
                  num="";
                  location=i;
                  }
                  if(i==str.length()-1)
                  {
                           for(int k=location+1;k<=i;k++)
                                    num=num+str[k];
         i_num.push_back(atoi(num.c_str()));
                   num="";
                   location=i;
                  }
         }
   for(int p=0;p<=4;p++)
   cout<<i_num[p]<<endl;
return 0;
}

c++ triangle

這是執行檔案，給大家下載去玩
https://skydrive.live.com/redir.aspx?cid=a4872f58128956b2&resid=A4872F58128956B2!268&parid=A4872F58128956B2!267&authkey=!APmGHg_J5c00EGw

下面則是列出MFC主要增加的部分

class CtriangleDlg : public CDialogEx                                //全域變數 抓輸入資料
{
public:
 int number;
        bool start;
//其他略
};

BOOL CtriangleDlg::OnInitDialog()                                  //初始化痊癒變數的數值
{
 start=0;
//其他略
}

void CtriangleDlg::OnPaint()
{
 if (IsIconic())
 {
  //略
 }
 else
 {
  CPaintDC pDC(this);
  if(start==1)                                                       //button按下時開始
  {
  pDC.MoveTo(100,500);     //初始的三點座標
  pDC.LineTo(300,100);
  pDC.LineTo(500,500);
  pDC.LineTo(100,500);
  if(number==0)
   ;
  else
   triangle(100,500,300,100,500,500,0,number,&pDC);
  }
  CDialogEx::OnPaint();
 }
}

void triangle(double x1,double y1,double x2,double y2,double x3,double y3,int count,int N,CPaintDC* draw)
{
 double leftx=(x1+x2)/2;
 double lefty=(y1+y2)/2;
 double rightx=(x1+x3)/2;
 double righty=(y1+y3)/2;
 double downx=(x2+x3)/2;
 double downy=(y2+y3)/2;
 draw->MoveTo(int(leftx),int(lefty));
 draw->LineTo(int(rightx),int(righty));
 draw->LineTo(int(downx),int(downy));
 draw->LineTo(int(leftx),int(lefty));
 count++;
 if(count<N)
 {
  triangle(leftx,lefty,x2,y2,downx,downy,count,N,draw);
  triangle(x1,y1,leftx,lefty,rightx,righty,count,N,draw);
  triangle(rightx,righty,downx,downy,x3,y3,count,N,draw);
 }
}

void CtriangleDlg::OnBnClickedButton1()
{
 CString tmp;
 GetDlgItemText(IDC_EDIT1,tmp);                    //抓取edit box的資料
 number= _ttoi(tmp.GetBuffer(0));
 start=1;
 Invalidate();                                                        //畫面清空重新畫圖
}

NCNU LISP hand write 1

Q:

(define (A x y )

   (cond((= y 0) 0)

            ((= x 0) (* 2 y))

            ((= y 1) 2)

            (else (A (- x 1)  (A x (- y 1 )))))

 )

(define (h n) (A 2 n ) )的結果&證明

A:

NCNU LISP HW3

exercise 3: linear recursive and linear iterative
                        but the function is changed:

            f(n) = n                        if n < 3 
                   2*f(n-1)+f(n-2)-f(n-3)   otherwise

(define (recursive x)
        (cond ((= x 0) 0)
              ((= x 1) 1)
              ((= x 2) 2)
              (else  (- (+ (* (recursive (- x 1)) 2) (recursive (- x 2)))
              (recursive (- x 3))))
        )
)
(define (interative x)
        (cond ((= x 0) 0)
              ((= x 1) 1)
              ((= x 2) 2)
              (else (do-interative 0 1 2 (- x 2)))
        )
)
(define (do-interative a b c x)
        (cond ((= x 0) c)
              (else (do-interative b c (- (+ (* c 2) b) a) (- x 1)))
        )
)

NCNU LISP HW2

exercise 2: improve the good-enough?


(define (square  x) (* x x))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))


(define (good-enough? guess x)
 (< (abs (- guess (improve guess x)))
    (* 0.0001 (improve guess x))))

(define (sqrt x)
  (sqrt-iter 1.0 x))

(define (abs x)
  (if (< x 0)
      (- x)
      x))

NCNU LISP HW1

exercise 1: calculate the sum of squares

(define (>= x y)(not (< x y)))
(define (square a)(* a a))
(define (answer x y z)
        (cond ( (and (>= x z) (>= y z)) (+ (square x) (square y)))
              ( (and (>= y x) (>= z x)) (+ (square y) (square z)))
              ( (and (>= z y) (>= x y)) (+ (square z) (square x)))
        )
)