樹心幽徑

20200701用JavaScript設計二分搜尋法
2020/06/30,21:55

(0-1)二分搜尋法所要搜尋的資料數列,要先排序才可行。

 

(0-2)要用二分搜尋法在給定的資料數列搜尋數字K,過程如下:

     「 將K和「數列的中間數」比較,
      如果二數相等,則在數列中找到有K,搜尋結束。
      如果K比中間數大,則往「大的那一方」找,
      如果K比中間數小,則往「小的那一方」找,
      如果待尋「那一方」不存在則搜尋結束。」
      不管往「大的那一方」或「小的那一方」搜尋皆採同上處理方式。

 

(1-1)在notepad輸入如下JS程式碼並存檔在桌面為bs01.htm

<script>
 

var a = [1, 13, 5, 26, 7 , 18 , 9];


function bsearch(k){
    document.write("<hr>數字k="+k+"的搜尋結果如下:");
    var L=0;
    var R=a.length-1;
    var M=(L+R)/2;
    while (L<=R){
            document.write("<br> L="+L+" a[L]="+a[L]+", R="+R+" a[R]="+a[R]+", M="+M+" a[M]="+a[M]+"");
            if (a[M]==k) {
            document.write("<br> 找到一筆匹配在 M="+ M + " a[M]="+a[M]);
                break;
            }
            else{
                if (k >a[M]) {
                    L=M+1;
                document.write("<br> k="+k+" > a[M]="+a[M]+" 往大的那一半找 => L="+L+" R=" +R + "<br>");
                    }
                else {
                    R=M-1;
                    document.write("<br> k="+k+" < a[M]="+a[M]+" 往小的那一半找 =>  L="+L+" R=" +R + "<br>");
                    }
            }
            M=(L+R)/2;
        }
       if (L>R) document.write(" <br> 因"+L+"=L  >  R="+R+" => [L,R]的數字區間不存在,故找不到k="+k);
}

a.sort(function(a, b){return a - b;});
document.write("二分搜尋法<br>待搜尋陣列a[]="+a);

var k= parseInt(prompt("請輸入k=","7"));
document.write("<HR>你輸入的k=" + k + "<br>");

bsearch(k);


</script>


(2) 用firefox開啟bs01.htm並輸入8,瀏覽結果如下:

二分搜尋法
待搜尋陣列a[]=1,5,7,9,13,18,26


你輸入的k=8


數字k=8的搜尋結果如下:
L=0 a[L]=1, R=6 a[R]=26, M=3 a[M]=9
k=8 < a[M]=9 往小的那一半找 => L=0 R=2

L=0 a[L]=1, R=2 a[R]=7, M=1 a[M]=5
k=8 > a[M]=5 往大的那一半找 => L=2 R=2

L=2 a[L]=7, R=2 a[R]=7, M=2 a[M]=7
k=8 > a[M]=7 往大的那一半找 => L=3 R=2

因3=L > R=2 => [L,R]的數字區間不存在,故找不到k=8

 

(3)按f5鍵重新整理firefox中的bs01.htm並輸入7,瀏覽結果如下:

二分搜尋法
待搜尋陣列a[]=1,5,7,9,13,18,26


你輸入的k=7


數字k=7的搜尋結果如下:
L=0 a[L]=1, R=6 a[R]=26, M=3 a[M]=9
k=7 < a[M]=9 往小的那一半找 => L=0 R=2

L=0 a[L]=1, R=2 a[R]=7, M=1 a[M]=5
k=7 > a[M]=5 往大的那一半找 => L=2 R=2

L=2 a[L]=7, R=2 a[R]=7, M=2 a[M]=7
找到一筆匹配在 M=2 a[M]=7

 

(3)

<script>
var a = [1, 5, 7 ,9,13, 18 , 26];

function bs(k){
    document.write("<hr>搜尋"+k+"如下:");
    var L=0;
    var R=a.length-1;
    var M=(L+R)/2;
    while (L<=R){
            if (a[M]==k) {
                document.write("找到"+k+"在a["+ M+"]處" );
                break;
            }
            else{
                if (k >a[M]) L=M+1;   else   R=M-1;
            }
            M=(L+R)/2;
        }
       if (L>R) document.write(" <br> 找不到 "+k);
}

document.write("<hr>a[]="+a+ ":");
var k= parseInt(prompt("k=","7"));
bs(k);
</script>

 

(4)

a[]=1,5,7,9,13,18,26:


搜尋7如下:找到7在a[2]處

 

REF-1:20200102用JavaScript設計二分搜尋法bs01.htm

20200619用JavaScript來編寫氣泡排序法及選擇排序法程式
2020/06/19,20:39

(1)IT重點:20200623ITLast.odt 下載 (16 KB) | created 23 六月, 2020

(1-1)在notepad輸入如下JS程式碼並存檔為d:\bsort.htm

<script>
var a = [9, 5, 8, 7, 6 , 4 ];
function bsort(){
    var size=a.length;
    document.write("待排陣列計有"+size+"個元素<br>");
    for (i=0;i<= size-2;i++){
        for (j=0;j<=size-2-i;j++){
            if (a[j]>a[j+1]) {
            document.write("交換前 at j=" + j + "(" + a[j] + "," + a[j+1] + ")");
                t=a[j];  a[j]=a[j+1];  a[j+1]=t;
        document.write("-->交換後 a[]="+a +"<br>");
            }
        else
            document.write("無交換 at j=" + j + "(" + a[j] + "," + a[j+1] + ")<br>");
        }
    document.write("<br>第"+ i +"回合結果: a[]="+a +"<HR color=green>");
    }
}

document.write("氣泡排序法排序前 a[]="+a+"<hr color=red>");
bsort();
</script>

 


 

(1-2)用firefox開啟d:\bsort.htm,瀏覽結果如下:

氣泡排序法排序前 a[]=9,5,8,7,6,4


待排陣列計有6個元素
交換前 at j=0(9,5)-->交換後 a[]=5,9,8,7,6,4
交換前 at j=1(9,8)-->交換後 a[]=5,8,9,7,6,4
交換前 at j=2(9,7)-->交換後 a[]=5,8,7,9,6,4
交換前 at j=3(9,6)-->交換後 a[]=5,8,7,6,9,4
交換前 at j=4(9,4)-->交換後 a[]=5,8,7,6,4,9

第0回合結果: a[]=5,8,7,6,4,9


無交換 at j=0(5,8)
交換前 at j=1(8,7)-->交換後 a[]=5,7,8,6,4,9
交換前 at j=2(8,6)-->交換後 a[]=5,7,6,8,4,9
交換前 at j=3(8,4)-->交換後 a[]=5,7,6,4,8,9

第1回合結果: a[]=5,7,6,4,8,9


無交換 at j=0(5,7)
交換前 at j=1(7,6)-->交換後 a[]=5,6,7,4,8,9
交換前 at j=2(7,4)-->交換後 a[]=5,6,4,7,8,9

第2回合結果: a[]=5,6,4,7,8,9


無交換 at j=0(5,6)
交換前 at j=1(6,4)-->交換後 a[]=5,4,6,7,8,9

第3回合結果: a[]=5,4,6,7,8,9


交換前 at j=0(5,4)-->交換後 a[]=4,5,6,7,8,9

第4回合結果: a[]=4,5,6,7,8,9


 

(2-1)在notepad輸入如下JS程式碼並存檔在桌面為ssort.htm

<script>
var b = [9, 5, 8, 1, 3 ];

function ssort(){
  var size=b.length;
  document.write("待排陣列計有"+size+"個元素<br>");

  for (i=0;i<size-1;i++){
        var mini=i;
        for (j=i+1;j<size;j++){
            if (b[j]<b[mini]) mini=j;
        }
        document.write("<br>i=" + i+ "交換前b[" + i + "]=" + b[i]+ ", b[" + mini+"]" + "=" + b[mini] + " mini=" +mini);

        t=b[mini];
        b[mini]=b[i];
        b[i]=t;
        document.write("<br>第"+i +"回合結果:b[]="+b +"<HR color=red>");
        }
}

document.write("選擇排序法排序前 b[]="+b +"<HR color=green>");
ssort();
document.write("<br>排序後 b[]="+b);
</script>

 

(2-2)用firefox開啟d:\ssort.htm,瀏覽結果如下:

選擇排序法排序前 b[]=9,5,8,1,3


待排陣列計有5個元素

i=0交換前b[0]=9, b[3]=1 mini=3
第0回合結果:b[]=1,5,8,9,3



i=1交換前b[1]=5, b[4]=3 mini=4
第1回合結果:b[]=1,3,8,9,5



i=2交換前b[2]=8, b[4]=5 mini=4
第2回合結果:b[]=1,3,5,9,8



i=3交換前b[3]=9, b[4]=8 mini=4
第3回合結果:b[]=1,3,5,8,9



排序後 b[]=1,3,5,8,9

 


REF1: 20191116用dev C++來編寫氣泡、選擇、插入排序法

REF2: 20191111用python設計氣泡排序法(採升序排列,ascending)

REF3:20191230用JavaScript設計插入與選擇排序法

20200616用python來可輸入產生費氏數列的程式
2020/06/16,20:50

(一)費氏數列由0和1開始,之後的費氏數字就是由之前的兩數相加而得出。

(1-1)首幾個費氏數字是: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……(參考維基百科)

(1-2)第n個費氏數字及第n-1個費氏數字的比例趨近於黃金比例(1.618...)。

 

(二)編寫python程式:

(2-1)由windows開始功能表執行 IDLE(python 3.7 64bit)

    安裝python請參考:20191014在windows7安裝並使用python3.7.4來剖析數字序列字串

(2-2)按CTRL+N在PYTHON文字編輯器編寫如下程式碼,並存為 d:\fib-1.py

def fib(n):
    if n<=1 :
        return n
    else:
        return fib(n-1)+fib(n-2)
   
n=int(input("請輸入n="))
while n >= 0 :
    print(fib(n))
    n=int(input("請再輸入n="))

 

(2-3)在PYTHON文字編輯器按F5可儲存編寫的程式碼並執行之,結果如下:

請輸入數字n=0
fib( 0 )= 0
請再輸入另一個n=1
fib( 1 )= 1
請再輸入另一個n=2
fib( 2 )= 1
請再輸入另一個n=3
fib( 3 )= 2
請再輸入另一個n=4
fib( 4 )= 3
請再輸入另一個n=5
fib( 5 )= 5
請再輸入另一個n=6
fib( 6 )= 8
請再輸入另一個n=7
fib( 7 )= 13
請再輸入另一個n=8
fib( 8 )= 21
請再輸入另一個n=9
fib( 9 )= 34
請再輸入另一個n=10
fib( 10 )= 55
請再輸入另一個n=11
fib( 11 )= 89
請再輸入另一個n=12
fib( 12 )= 144
請再輸入另一個n=13
fib( 13 )= 233
請再輸入另一個n=14
fib( 14 )= 377
請再輸入另一個n=-1


(三)編寫python程式:

(3-1)按CTRL+N在PYTHON文字編輯器編寫如下程式碼,並存為 d:\fib-2.py

def fib(n):
    if n<=1 :
        return n
    else:
        return fib(n-1)+fib(n-2)
   
n=int(input("請輸入數字n="))
cs = []
while n >= 0 :
    x=fib(n)
    print("fib(",n,")=",x)
    cs.append(x)
    print ("cs[]=",cs)
    n=int(input("請再輸入另一個n="))
   
(3-2)在PYTHON文字編輯器按F5可儲存編寫的程式碼並執行之,結果如下:

請輸入數字n=0
fib( 0 )= 0
cs[]= [0]
請再輸入另一個n=1
fib( 1 )= 1
cs[]= [0, 1]
請再輸入另一個n=2
fib( 2 )= 1
cs[]= [0, 1, 1]
請再輸入另一個n=3
fib( 3 )= 2
cs[]= [0, 1, 1, 2]
請再輸入另一個n=4
fib( 4 )= 3
cs[]= [0, 1, 1, 2, 3]
請再輸入另一個n=5
fib( 5 )= 5
cs[]= [0, 1, 1, 2, 3, 5]
請再輸入另一個n=6
fib( 6 )= 8
cs[]= [0, 1, 1, 2, 3, 5, 8]
請再輸入另一個n=7
fib( 7 )= 13
cs[]= [0, 1, 1, 2, 3, 5, 8, 13]
請再輸入另一個n=8
fib( 8 )= 21
cs[]= [0, 1, 1, 2, 3, 5, 8, 13, 21]
請再輸入另一個n=9
fib( 9 )= 34
cs[]= [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
請再輸入另一個n=-1


20200604用DEV-C++設計C++STL堆疊及佇列程式
2020/06/04,21:43

如沒有DEV-C++ C語言編譯開發環境(SDK),請先下載Dev-Cpp 5.11 TDM-GCC 4.9.2 Setup.exe(約49MB)並安裝之

(一)C++ STL堆疊程式:

(1-0) 堆疊資料結構,只能自頂端推入(PUSH)元素,也只能自頂端移走(POP)元素,先進後出。

(1-1)例子:

將如下3數1、2、3依序推入堆疊S中,再自S取出二個,

再將4、5、6依序推入堆疊S中,再自S取出1個,

再將7、8、9依序推入堆疊S中,再自S取出2個,

最後的S為何?  答:「頂端:7 5 4 1」

會依序取出的數為何?  答:「3 2 6 9 8」


(1-2)執行DEV-C++並按CTRL+N編寫如下程式碼並存為 d:\s1.cpp

 

#include <stack>
#include <iostream>
using namespace std;
int main(){
    stack<int> s;
    printf("\n推入10個立方數到堆疊s中:\n<s底端:");
    for (int i=0;i<10;i++) {
        int x=i*i*i;
        printf("%3d : ",x);
        s.push(x);
    }
    printf(":s頂端>\n將堆疊s中的數一一取出如下:\n");
    while (not s.empty()){
        int y=s.top();
        printf("將s頂端元素(%3d)取出前, s有%3d個元素  \n", y,s.size());
        s.pop();                 
    }
}


(1-3)按F11編譯並執行s1.cpp,會於新視窗上輸出結果如下:


推入10個立方數到堆疊s中:
<s底端:  0 :   1 :   8 :  27 :  64 : 125 : 216 : 343 : 512 : 729 : :s頂端>
將堆疊s中的數一一取出如下:
將s頂端元素(729)取出前, s有 10個元素
將s頂端元素(512)取出前, s有  9個元素
將s頂端元素(343)取出前, s有  8個元素
將s頂端元素(216)取出前, s有  7個元素
將s頂端元素(125)取出前, s有  6個元素
將s頂端元素( 64)取出前, s有  5個元素
將s頂端元素( 27)取出前, s有  4個元素
將s頂端元素(  8)取出前, s有  3個元素
將s頂端元素(  1)取出前, s有  2個元素
將s頂端元素(  0)取出前, s有  1個元素

(1-4)按CTRL+N編寫如下程式碼並存為 d:\s2.cpp

#include <stack>

#include <iostream>

using namespace std;

int main(){   

stack<int> s;   

printf("\n推入1,2,3\n");  s.push(1);   s.push(2);   s.push(3);      

printf("取出(%d)\n", s.top());   s.pop();                   
printf("取出(%d)\n", s.top());   s.pop();                 

printf("\n推入4,5,6\n");   s.push(4);   s.push(5);   s.push(6);   

printf("取出(%d)\n", s.top());   s.pop();                       

printf("\n推入7,8,9\n");   s.push(7);   s.push(8);   s.push(9);   

printf("取出(%d)\n", s.top());   s.pop();    

printf("取出(%d)\n", s.top());   s.pop();              

}

(1-5)按F11編譯並執行s2.cpp,會於新視窗上輸出結果如下:


推入1,2,3
取出(3)
取出(2)

推入4,5,6
取出(6)

推入7,8,9
取出(9)
取出(8)

(二)C++ STL佇列程式:

(2-0) 佇列資料結構,自後端推入(PUSH)元素,自前端移走(POP)元素,先進先出。

(2-1)例子:    

將如下3數1、2、3依序自後端推入佇列Q中,再自Q前端取出二個,

再將4、5、6依序推入佇列Q中,再自Q取出1個,

再將7、8、9依序推入佇列中,再自Q取出2個,

最後的Q為何?  答:「後端: 9  8 7 6  :前端」

會依序取出的數為何?  答:「1 2 3 4 5」


(2-2)執行DEV-C++並按CTRL+N編寫如下程式碼並存為 d:\q1.cpp

#include <queue>
#include <iostream>
using namespace std;
int main(){
    queue<int> q;
    printf("\n插入10個平方數到佇列q中:\n <q前端:");
    for (int i=0;i<10;i++) {
        int x=i*i;
        printf("%3d : ",x);
        q.push(x);
        }
    printf(":q後端>\n將q中元素一一自前端取出如下:\n");
    while (not q.empty()){
        int y=q.front();
        printf("將q最前端元素(%2d)取出前, q有%2d個元素\n",y,q.size()); 
        q.pop();                  
    }
    printf("q.size()=%d\n",q.size());
}

(2-3)按F11編譯並執行q1.cpp,會於新視窗上輸出結果如下:


插入10個平方數到佇列q中:
 <q前端:  0 :   1 :   4 :   9 :  16 :  25 :  36 :  49 :  64 :  81 : :q後端>
將q中元素一一自前端取出如下:
將q最前端元素( 0)取出前, q有10個元素
將q最前端元素( 1)取出前, q有 9個元素
將q最前端元素( 4)取出前, q有 8個元素
將q最前端元素( 9)取出前, q有 7個元素
將q最前端元素(16)取出前, q有 6個元素
將q最前端元素(25)取出前, q有 5個元素
將q最前端元素(36)取出前, q有 4個元素
將q最前端元素(49)取出前, q有 3個元素
將q最前端元素(64)取出前, q有 2個元素
將q最前端元素(81)取出前, q有 1個元素
q.size()=0

 

(2-4)執行DEV-C++並按CTRL+N編寫如下程式碼並存為 d:\q2.cpp

#include <queue>

#include <iostream>

using namespace std;

int main(){    

queue<int> s;    

printf("\n推入1,2,3\n");    

s.push(1);   s.push(2);   s.push(3);        

printf("取出(%d)\n", s.front());   s.pop();                     

printf("取出(%d)\n", s.front());   s.pop();                     

printf("\n推入4,5,6\n");    s.push(4);   s.push(5);   s.push(6);    

printf("取出(%d)\n", s.front());   s.pop();                         

printf("\n推入7,8,9\n");    s.push(7);   s.push(8);   s.push(9);    

printf("取出(%d)\n", s.front());   s.pop();     

printf("取出(%d)\n", s.front());   s.pop();     

}

(2-5)按F11編譯並執行q2.cpp,會於新視窗上輸出結果如下:


推入1,2,3
取出(1)
取出(2)

推入4,5,6
取出(3)
推入7,8,9
取出(4)
取出(5)


REF1: https://larry850806.github.io/2016/06/06/STL1/

 
Accessible and Valid XHTML 1.0 Strict and CSS Powered by LifeType