UVA 272 C++

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=208

#include<iostream>
#include<string>
using namespace std;
int main()
{
string input = "";
string output="";
int count = 0;
//cin >> input;
while (getline(cin, input))
{
output = "";
for (int i = 0; i <= input.length() - 1; i++)
{
if (input[i] == '\"')
{
count++;
if (count % 2 == 1)
output = output + "``";
else
output = output + "''";;
}
else
output = output + input[i];
}
cout << output << endl;
}
return 0;
}

複雜度筆記

○(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))
)
)