顯示具有 程式概念 標籤的文章。 顯示所有文章
顯示具有 程式概念 標籤的文章。 顯示所有文章

2018年12月4日 星期二

二元樹&排序Binary search tree

演算法 & 資料結構

#自己的定義
電腦的資料說穿了就只有0和1,怎麼擺放0和1就是資料結構。
怎麼用和算就是演算法。

電腦要如何完成「排序」(sort) 這件工作呢?「二元樹」 (binary tree) 怎樣子應用在排序這項工作呢?

二元樹是數據結構。 它的關鍵特徵是樹中的每個節點最多可以有兩個子節點,它們按值排列,左邊的子節點值較低,右邊節點較高。

樹狀結構Trees

樹柱結構是一種非線性結構。例如族譜,組織架構。在資料科學方面可以應用到電腦的作業系統和資料庫管理。像我們最常看的排序就是一種運用。
Decision tree
當然機器學習中的決策樹也是一種應用

Binary Tree: Traversal(尋訪)
連結串列Linked list

樹的結構與規範

01. 樹根root
02.節點node
node為n個互斥的集合,n>=0,互斥的集合也是一棵樹稱為子樹
03.不能有重邊
04.不能有迴圈
05.不能不連通
06. 分支度(Degree)
07. 階層(Level)
08. 高度(Height)
09. 終端節點(Terminal Nodes)
10. 父節點(Parent)
11.  子節點(Children)

建立一排數列為: 55,70,30,65,20,25,35,85

*中序法依序排列
root=55
70>55,在55右邊
30<55,在55左邊
65>55,在55右邊,但65<70,在70左邊
以此類推



#python二元樹排序
*定義Tree
class Node:
         def __init__(self, val):
            self.l_child = None
            self.r_child = None
            self.data = val
*插入node
r = Node(55)
binary_insert(r, Node(70))
binary_insert(r, Node(30))
binary_insert(r, Node(65))
binary_insert(r, Node(20))
binary_insert(r, Node(25))
binary_insert(r, Node(35))
binary_insert(r, Node(85))

def binary_insert(root, node):
       if root is None:
             root = node
       else:
           if root.data > node.data:
                  if root.l_child is None:
                        root.l_child = node
                  else:
                        binary_insert(root.l_child, node)
           else:
                  if root.r_child is None:
                        root.r_child = node
                  else:
                        binary_insert(root.r_child, node)

def in_order_print(root):
       if not root:
             return
       in_order_print(root.l_child)
       print(root.data)
       in_order_print(root.r_child)

def pre_order_print(root):
       if not root:
             return
       print(root.data)
       pre_order_print(root.l_child)
       pre_order_print(root.r_child) 

in_order_print(r)

2018年12月1日 星期六

Recursion遞迴

遞迴是那些聽起來比實際更令人生畏的概念之一。老實說。要利用它,你不需要掌握複雜的數學思想;或者從四個維度開始思考;或者一個接一個地接受某個人的夢想將一個想法植入他們的潛意識中,或甚至理解遞迴的含義。

在大多數情況下,遞迴的許多用法都有很好的參考文件和實例。然後,你可以將它們複製並貼上到程式碼中,而無需了解它們的運作的方式,也不用知道它們為什麼要這樣做。但如果你這樣做,你會錯過很有意思的遞迴。在編寫幾行程式碼後,遞迴是讓CPU完成困難度高的工作的最佳方法之一;因此,它可以幫助你避免在沒有遞迴的情況下需要或可能去解決更複雜的問題。

這是因為遞迴是通過重複一個簡單函數來解決更複雜問題的一種方法。訣竅是這個功能函數從內部作迴圈。它不是從另一個函數起動運行原函數,而是從自己的代碼中調用自己的另一個自己。這種programming相當於將兩個鏡像子面對面創建出看似無限的鏡子,遞迴的一個經典且最簡單的示例是一個函數的階乘。正整數的階乘。例如,4的階乘是4x3x2x1,等於24

#用for寫階乘
<?php
function factorial($n){
    $result = 1;
    for ($i=2; $i<=$n; $i++) {
            $result *= $i;
    }
return $result;
}
echo factorial(4);
?>

#用遞迴寫階乘
<?php
function factorial($n) {
    return $n == 0 ? 1 : $n*factorial($n-1);
}
echo factorial(4)."<br>";
?>

#費氏數列Fibonacci Sequence:
兔子繁殖說明
Fn=Fn-1+Fn-2,n>=3
F1=F2=1
1->1->2->3->5->8->13->21(從3開始每一項都是前兩項之和)

#python費氏數列:
def Fib(n):
if n == 0:
return 0;
elif n == 1:
return 1;
return Fib(n-1) + Fib(n-2)

print(Fib(4))

#遞迴樹Recusive Trees
從上面的圖可以觀察到,每一次函式往下的呼叫,最後都會停在 Fib(1) 或 Fib(0),因為這兩項是唯一在計算費氏數列時先被定義的。因此找到這兩項後,就可以開始往前加總出其他項的值,而往前加總的順序如下:
由圖可知Fib(4)共呼叫9次
f(0) = 0 , 1次
f(1) = 1 , 1次
f(2) = f(0) + f(1) , 1+1+1=3 次
f(3) = f(2) + f(1) , 3+1+1=5 次
f(4) = f(3) + f(2) , 5+3+1=9 次

因此導出呼叫次數為 "f(n)=f(n-1)+f(n-2)+1"
就
費氏數列後面再加個1就是答案了  

自然界實例
有趣的是,如果初生結構之間的角度是黃金角度,螺旋線的數目就往往是「費氏數列」中的數。費氏數列最先由13世紀的意大利數學家萊奧納爾多·斐波那契提出。這個數列中,在1之後的每個數都是前兩個數的和,即是1,1,2,3,5,8,13,21,34,55……如此類推。

許多呈螺旋圖案的植物,花瓣數目往往是費氏數列中的數。有些人觀察到,毛茛的花有5塊花瓣,美洲血根草有8塊,柳蘭有13塊,紫菀有21塊,春白菊有34塊,美國紫菀則有55塊或89塊。(圖六)在水果和蔬菜中也可以找到跟費氏數列有關的數字。例如,香蕉的橫切面是一個五邊形。






2018年11月30日 星期五

堆疊(Stack)& 佇列(Queue)

在解釋基本程式概念時,很難知道從哪裡開始。當有人開始編碼時,有大量不同的想法需要理解,吸收並最終轉化為解決方案。這取決於您所選語言的語法和特性。

最好的方法之一就是通過練習題來開始編寫程式碼。好像購物清單的使用,無論度假還是超市購物。程式碼中的列表邏輯就像在現實生活中清單一樣。清單很容易處理瑣事和片段的記憶。例如,在Python中,您可以如此建立一個購物清單(陣列)

shoppinglist = ["rice","salt","oil"]
print(shoppinglist)
['rice', 'salt', 'oil']

push() pop()
3.oil
2.salt
1.rice

這是一個陣列,因為每個值本身就是一個字串。但是陣列是動態的,您經常要做的第一件事就是新增資料,如何增加新資料是一個學問。例如,CPU如何增加法運算速度更快,或是以最好的方式將資料放在記憶體內,是從後面加好呢,還是從前面加。

堆疊
網路上大部分的人都是用疊書來做比喻,疊最高的也就是最後一本必須先拿,成為後進先出LIFO(Last In First Out)或者先進後出FILO(First In Last Out)的例子。我們也可以把它想做是Linux command列的歷史紀錄查詢一樣我們會先查最後一筆然後一直往上查,或是查看瀏覽器之前看過的頁面可以用上一頁網上查做作為後進先出的例子。

Python中可用append增加一筆資料
shoppinglist.append("tea")
print(len(shoppinglist))
4

push() pop()
4.tea
3.oil
2.salt
1.rice

Python中可用pop()取出一筆資料
shoppinglist.pop()  
print(shoppinglist)
['rice', 'salt', 'oil']

a stack
push() pop()
4.tea
3.oil
2.salt
1.rice

push()
將資料放入堆疊頂端
pop()
取出堆疊頂端之資料

心得
從最後一筆取得資料的時候處理器可以處理的較快。另外,索引也不用重建。

應用..........
CPU中斷處理
遞迴程式
十進位轉二進位
套環遊戲
字串反轉

佇列
a queue
先進先出法FIFO(First In First Out)
雖然新增或移除資料時,同步修改索引位址,浪費資源。但今日處理器的速度已經不在乎是先進先出或後進先出

shoppinglist.pop(0)     
'rice'
從第1筆取出
print(shoppinglist)     
['salt', 'oil']

pop() 1.rice 2.salt 3.oil push()

for x in range(0,len(shoppinglist)):
...  shoppinglist[x]
...  print
... 
'salt'
'oil'

陣列的建立會有一個索引來記錄目前所指到的位址,新增或移除資料時,同步修改索引位址

應用..........
大多數的程式運用

2018年10月26日 星期五

regex(正規表達式)

正規表達式(regex或簡稱regexp)
是用於描述搜索模式的特殊文本字符串。  您可能熟悉萬用字元,例如* .txt,以查找文件管理器中的所有文本文件。 正規表達式等於 ^.*\.txt$

常用字元
?   (前面的字元可有可無)
\   (跳脫)
.   Match any single character(符合任何單個字元,例如a.b可符合acb,a1b)
\.  (cancel regex dot)
*  (the previous character can be null,repeated 1 time,2 time,any time)
+  (the previous character can be null,repeated 1 time,2 time,any time)
^  Match the empty string that occurs at the beginning of a line or string(字串開始)
$   Match the empty string that occurs at the end of line(字串結束)
\b  (邊界)
\B
\d or [0-9] Match any single digit.
\D Match any single non-digit character.
\s or \t\n  (任何一個空白字元)
[xyz]
[^xyz]
[a-z]
[^a-z]
[A-Z]


e.g.
grep -i word regex.txt
(find the words in regex.txt contain 'word' string)

grep -E '^word' regex.txt
(The option -E specifies a regex. )
(find the words begin with word.

e.g.
grep ^root /etc/passwd
(find each line start with 'root')

grep :$ /etc/group
(find each line end with)

grep '\<c...h\>'
(find start with c end with h and 5 letters)

e.g.
find 'color' or 'colour' in a text file
use colou?r

e.g.
find 'ports' or 'port' in export,portable,important
use \bports?\b

e.g.
find TPE,KHH,LAX in a text file
use \b[A-Z][A-Z][A-Z]\b

e.g. 
find phone numbers
use 09\d\d-?\d\d\d-?\d\d\d

e.g.
search all ip address
use \d+\.\d+\.\d+\.\d+
(\. means escape dot)

e.g.
delete  all space in a text file
delete ^\s*$

e.g.
find email address
\ b [A-Z0-9 ._%+ - ] + @ [A-Z0-9 .-] + \. [AZ] {2,} \ b

2018年10月23日 星期二

notes(雜記)

Library or api or framework
Library
是一堆function,您可以使用自己的程式碼呼叫它們,以幫助您更快/更輕鬆地完成工作。 例如,network(socket) library將提供加載和操作網路底層的function,從而使您不必為自己編寫所程式碼。

API
(應用程序編程接口)是一個術語,表示Library中的函數/方法,您可以呼叫它來為您執行操作。

framework
是一個提供許多服務的大型library(而不是像大多數Library那樣只有一個集中的能力)。


SDK or IDE
SDK
Software Development Kit(軟件開發工具包),SDK具有DLL庫,編譯器和其他工具,用於將源代碼編譯為可執行程序(或在JVM或.NET上運行的中間字節代碼)。 您可以在任何文本編輯器中編寫源代碼,並使用SDK從所有文本文件構建程序。ex: NET Framework 4.0和Swing Application Framework
IDE
Integrated Development Environment(綜合發展環境),IDE將所有這些SDK功能(包括編譯器)集成到GUI菜單中,以便更輕鬆地訪問所有這些功能並更輕鬆地開發軟件。 它為您創建構建腳本,使您可以更輕鬆地管理項目。ex: Visual Studio,Eclipse


大括號,中括號和小括號在程式中常用法(brackets)
{} 大括號
大括號用於組合聲明和語句。
類別或接口的內容用大括號括起來。
方法和構造函數用大括號括起來。
大括號用於在if語句,循環或其他控制結構中對語句進行分組。
[]中括號(“方括號”)
中括號用於索引到一個數組中。
()小括號
括號用於兩個目的:(1)控製表達式中的操作順序,(2)將參數提供給構造函數或方法。


免安裝軟體Portable Software
免安裝軟體把會用到的 DLL 都打成一包和執行檔放在一起,程式啟動時就用預設的「相同路徑」去尋找 DLL,使用者不需要「安裝」這個步驟就能夠直接使用。


跨平台Cross-platform
純C++ or C的程式,沒有用到windows平台的API(for example: DirectX)
大致可以跨平台

code editor
mac:
1. BBEdit
2. textmate
win:
1. UltraEdit
2. notepad++(外掛)
linux:
vi
note:
Syntax Highlighting
行數
indent
Word completion, Function completion  
Function parameters hint

向下相容
1. 好處,永續經營 
2. 缺點,程式越來越龐大
程式語言沒向下相容的例子,paython2 to 3

Java Runtime Environment 32bit & 64bit
32bit
for browser
64bit
for system

2018年10月22日 星期一

換行(newline,linebreak)

<br /> 是一個HTML換行符
 換句話說,當您將頁面視為呈現的HTML時,<br />將創建一個新行。

\ n是源代碼中的換行符
而當您查看源代碼時,\ n將創建一個新行。

或者,如果您輸出到CLI而不是將由Web瀏覽器呈現的某個位置,則\ n將在CLI輸出中創建換行符。

e.g.
<?php
echo " 換行<br />";
?>

in CLI
 <?php
#!/usr/bin/php
<?php
echo " 換行\n";
?>

Comment syntax(程式的註解)

Bash
#This is a comment.

PHP 
// This is a single-line comment.
# This is also a single-line comment.

/*
This is a multiple-lines comment block.
*/

Python
# This is a comment.

""" 
This is a multiple-lines comment block.
"""
 

HTML 
<!--This is a comment.-->
 

Jacascript
// This is a single-line comment./*
This is a multiple-lines comment block.
*/

CSS

/*
This is a multiple-lines comment block.
*/

Perl
#This is a comment. 

C
 /* This is a comment.*/

C++
 // This is a single-line comment.

2017年12月18日 星期一

函式(function)

自訂與內建函式
#include "/usr/include/stdio.h"
int max(int a, int b) {

    int c;
    if (a>b) c=a;
    else c=b;
    return c;
}
main(void)
 {
   int x=20,y=30;
   int d=max(x,y);
   printf("The max number is: %d\n",d);
 }


php
#!/usr/bin/php
<?php

 function max_num($a,$b) {
  if ($a>$b) {
     $c=$a;
     }
  else {
     $c=$b;
  }
  return $c;
 }

  echo max_num(3,2)."\n";
?>

shell script
#!/bin/bash

 max_num() {
  if [ $1 -gt $2 ]
  then
  c=$1
  else
  c=$2
  fi
  return $(($c))

}

max_num 10 20
echo $c









2017年11月29日 星期三

字元變數(variable)

建立變數

int i;
int j;
i=1;
j=2;

short way
int i=1, j=2;

字'元'變數

 一個英文字母、數字或其他的符號,我們稱它為字元(character),總共256種。可以用ASCII字元碼來對應到每個字元。要表示一個字元,我們可以用一對單引號 ' 把該字元夾起來,例如:
char test='c'; 
事實上,字元在電腦中是以一個八位元的整數來儲存(即 1 Byte)也就是說,其實字元對電腦來說也是一個數字,因為最後還是01的變化。

ASCII

 二進位               十進位           圖形
0000 0010            3
0011 0011            51                 3


main(void)
  {
   int e=3;
   printf("整數變數的值是(顯示圖形) : %c\n",e);

   char f='3';
   printf("
字元變數的值是(顯示十進位) : %d\n",f);

 }
 

第一個答案是空的,因為以%c顯示字元圖形是空的
整數變數的值是(顯示圖形) :

第二個答案是51,因為以%d顯示十進位的值
字元變數的值是(顯示十進位) :51

 結論:
 字元在電腦中是以一個八位元的整數來儲存(例如ASCII所示)

因此也可以拿來做加減乘除等四則運算。例如

ASCII

 二進位               十進位           圖形
0011 0001            49                 1
0011 0100            52                 4
#include <stdio.h>
main(void)
 { char c='1';
   c=c+3;
   printf("The answer is : %c\n",c);

  char d='1';
   d=d+3;
   printf("The answer is : %d\n",d);
 }

The answer is : 4
The answer is : 52


控制字元

控制字元通常以跳脫字元 \ 開頭,簡單來說用'\n'控制換行就好像鍵盤按下Enter。

'\0'    空字元,用於字串的結束
'\n'    New Line,換行符號
'\r'    Carriage Return,回歸鍵(即 Enter 鍵)
'\t'    Tab,跳格
'\b'    Backspace,倒退鍵
'\a'    Bell,嗶一聲
'\\'    反斜線 \
'\''    單引號 '
'\"'    雙引號  "

2016年10月22日 星期六

迴圈


1. For 迴圈 
若於程式設計階段已知要執行的次數 則可使用for敘述
for 固定變量,限定數值範圍 (適用數值變量)
for start,end,step start,end,step都必須是數字

#!/bin/bash
for ((i=0; i<10; i++))
do
echo $i;
done

#!/bin/bash
Distro=('openSUSE' 'Red hat' 'Debian' 'Ubuntu' 'Fedora')
for ((i=0;i<${#Distro[@]};i++))
do
  echo "Linux Distro[$i]=>"${Distro[$i]}
done

#!/usr/bin/perl
@array = ('openSUSE', 'Red hat', 'Debian', 'Ubuntu', 'Fedora');
$length = @array;
for ($i=0;$i<$length;$i++)
{
print "$array[$i]\n";
}

 2. While迴圈
若未知執行次數的話 則應使用while或repeat
while迴圈 稱為前測試迴圈
while 限定條件
while(xx) xx可以是任何運算式
也就是說 先測試條件運算式為真時 繼續執行迴圈 也有可能不執行迴圈內容就直接離開

#!/bin/bash
i=0
while [ $i -lt 10 ];
do
   echo $i;
   ((i++))
done

#!/bin/bash
Distro=('openSUSE' 'Red hat' 'Debian' 'Ubuntu' 'Fedora')
i=0
while [ $i -lt ${#Distro[@]} ]
do
  echo "Linux Distro[$i]=>"${Distro[$i]}
  ((i++))
done

#!/usr/bin/perl
@array = ('openSUSE', 'Red hat', 'Debian', 'Ubuntu', 'Fedora');
$length = @array;
$i=0;
while ($i<$length)
{
print "$array[$i]\n";
$i++
}


3. do while迴圈
repeat   稱為後測試迴圈
也就是說 先執行迴圈 待條件運算式為真時再離開迴圈 也就是 迴圈內容至少執行一次


4. foreach迴圈 
foreach提供陣列很便利的輸出方式,
foreach 語法結構說明:
 
  結構一:
         每跑一圈foreach會把陣列($array)的陣列值
        (array value)存放到 $value 中。
 
         foreach ( $array as $value )
                     ... 執行程式碼 ...
  結構二:
        與結構一的意思一樣,但多增加了把陣列的所引
      (array key)'會同時將array key 取出並存放於
       $key 中。
   
       foreach ( $array as $key => $value )
                  ... 執行程式碼 ...

#!/usr/bin/php
<?php
$dataArray=array('openSUSE', 'Red hat', 'Debian', 'Ubuntu', 'Fedora');
foreach($dataArray as $daKey => $daValue)
{
 echo "\$dataArray[$daKey]=>".$daValue."\n";
}
?>

#!/usr/bin/perl
@array = ('openSUSE', 'Red hat', 'Debian', 'Ubuntu', 'Fedora');
foreach my $i (@array)
{
  print "$i\n";
}