日常隨筆: 6月 2015

2015年6月30日星期二

[Javascript]用Javasrcript實作樂透抽取程式

接續Java樂透的程式，解說就請參考Java那邊
要看結果請點下面網頁
結果如此網頁



<html>

<head lang="zh-tw">

<meta charset="UTF-8">

<title>JavaScript Test</title>

<style> 


.type{

border:1px solid #FFC010;

border-radius: 15px;

width: 500px;


}


.title{

width:300px;

border-bottom:1px solid #000000;

border:3px;

padding:right;

}

.t {

width:100px;

float:left;

margin: 10px;

text-align: right;

vertical-align:center;


}


</style>


<script>



function check(){

if(parseInt(reg.balls.value)>=parseInt(reg.token.value)){

takeBalls(reg.balls.value,reg.token.value);

}else {

window.alert("輸入的內容無法進行抽取喔~");

}      

return undefined;

}



function takeBalls(balls, token){

var result = new Array(token);


//document.write("<div style=\"border:2px solid #FFCC00; width:400px;border-radius: 20px;text-align: center; \">")

document.getElementById("resultset").innerHTML = '<p style="color:#00DDAA">抽取結果如下</p>';

//document.write("<p style=\"color:#00DDAA\">抽取結果如下</p>");

for(var i=0;i<token;i++){

result[i]=parseInt(Math.random()*balls+1);

for(var j=0;j<i;j++){

if(result[j]==result[i]){

i--;

}

}

}

result.sort(sortNumber);

for (var i = 0; i < token; i++) {

var OriginalFont = document.getElementById("resultset").innerHTML;

document.getElementById("resultset").innerHTML = OriginalFont + '<span style="color:#3377FF ">' + result[i] + '號</sapn>';

//document.write("<span style=\"color:#3377FF \">"+result[i]+"號</sapn>");

}


//document.write("<br><a href=\"js.html\">返回</a></div>");


return undefined;

}

function sortNumber(a,b)

{

return a - b;

}


</script> 



</head>


<body>




<form action="#" method="post" name="reg">

<fieldset class="type">

<legend>樂透抽取程式</legend>

<div class="title">   

<label class="t">總共號碼數</label><input type="number" name="balls" min="1" required="required">

</div>

<br>

<div class="title">

<label class="t">取球數</label><input type="number" name="token" min="1" required="required">

</div>

<br>



<input type="button" value="確認" onclick="check()" >

<input type="reset" value="清除">  

<br>

<center id="resultset"></center>

</fieldset>




</form>




</body>


</html>

[Java]樂透抽取程式

這是一個很經典的題目，從1~49，
隨機抓取六個不同的數字
在Java上要隨機抽取數字不難，用 java.util.Random()或是Math.random()都可以
我是習慣用Math.random()這個方法
Math.random()的取值是0<=Math.random()<1，所以要取1~49必須要寫成
Math.random()*49+1，那個範圍在0<=Math.random()*49+1<50
接著傳出的數值是double，所以要轉成int，取六個數字的程式碼就會變成這樣

  int[] random = new int[6];

  for(int i=0;i<6;i++){

   random[i]=(int)Math.floor(Math.random()*49+1);

   

  }

接著上述抽取的數字會有重覆的問題，最簡單的解法就是去找之前的數字有沒有重覆，有重覆就重抽一個數字，如範例：

public class Random {



 public static void main(String[] args) {



  int[] random = new int[6];

  for(int i=0;i<6;i++){

   random[i]=(int) Math.floor(Math.random()*49+1);   

   for(int j=0;j<i;j++){//檢查有無重覆

    if(random[i]==random[j]){//有重覆重抽一次

     i--;

     break;

    }   

   }   

  }

  System.out.println("result is:");

  for(int x=0;x<6;x++){

   System.out.print(random[x]+" ");

  }

 }

}

這個方法有個小缺點，比如說1000顆球取一千顆時，後面會重覆過多一直重抽數字
如果要解決這個情形可以用以下的解法
比如說10顆球抽3顆。一開始我們先將陣列排好成下面這樣
1 2 3 4 5 6 7 8 9 10
隨機1~10，假設抽到的是7號，我們就將第1個位置跟第7個位置交換
7 2 3 4 5 6 1 8 9 10
接著隨機2~10，假設抽到的是5號，接著將第2個位置跟第5個位置交換
7 5 3 4 2 6 1 8 9 10
再來隨機3~10，抽到的如果是5號，就將第3個位置跟第5個位置交換
7 5 2 4 3 6 1 8 9 10
最後抽到的三顆球就是打底線這三顆

最後我將總共的球數和抽取球數寫成鍵盤輸入，程式碼如下：

public class RandomApi {

 

 public static void main(String[] args) { 

  Scanner input = new Scanner(System.in);

  System.out.println("please input the number of balls:");

  int balls= input.nextInt();

  System.out.println("please input how many balls you want to pick:");

  int picks= input.nextInt();

  int [] result = RandomNumberPerduce(balls, picks);

  for(int i=0;i<picks;i++){

   System.out.print(result[i]+" ");

  }

  input.close();

 }

  

 

 //random value

 private static int[] RandomNumberPerduce(int x1, int x2){

    

  int[] random= new int[x1];

  if(x2>x1){

   System.out.println("Sorry, the number of balls is less then the number you want to pick up");

   return random;

  }

  for(int i=0;i<x1;i++){

   random[i]=i+1;

  }

  

  for(int i=0;i<x2;i++)

  {

   int result=(int) Math.floor(Math.random()*(x1-i)+i);

   int temp = random[result];

   random[result]=random[i];

   random[i]= temp;

   

  }

  return random;

 }

 

  

}//end of class

2015年6月29日星期一

[Java]讀取鍵盤輸入

Java裡面讀取鍵盤輸入的方法有兩種，一種是Scanner，一種是InputStreamReader

首先我們先介紹Scanner
Scanner可以生成一個物件然後用.next方法輸入string，或是用.nextInt方法等等輸入不同的資料型別。這方法會有一個

import java.util.Scanner;



public class scannerDemo {

 public static void main(String[] args) {

  Scanner input = new Scanner(System.in);

  

  System.out.println("Please type some words:");

  String str = input.next();

  System.out.println("The words you have typed is:"+str);

  

  System.out.println("Please type an integer x:");

  int x = input.nextInt();

  int sum=0;

  for(int i=1;i<=x;i++){

   sum=sum+i;   

  }

  System.out.println("The sum of 1 to x is:"+sum);

  input.close();



 }



}

再來是InputStreamReader
因為要使用一次讀一行的指令所以需要用到BufferReader
new BufferedReader(new InputStreamReader(System.in))這種語法其實是要看成
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader bfr = new BufferedReader(isr);兩行
不過這種寫成一行的語法沒有isr可以用就是了(雖然也沒有要用)，
這方法按ctrl+z可以終止輸入。

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;



public class inputStreamReaderDemo {



 public static void main(String[] args) throws IOException {

  BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));

  System.out.println("Input string and exit by ctrl+z");

  String str = bfr.readLine();

  

  //while intput "ctrl+z" the program will stop

  while(str!=null){

   System.out.println(str);

   str = bfr.readLine();

  }

  System.out.println("End of input");

  bfr.close();

  

      

 }



}

2015年6月28日星期日

關係(Relation) (一)：equivalence relation(等價關係)

在數學上我們會研究集合與集合之間的關係，關係有分成同一個集合之間元素的關係，已經不同集合之間元素的關係。兩個集合之間的關係我們稱之為二元關係(binary relation)，像是整數跟整數之間有大於這種關係(EX：1>-1,5>3,5>2等等) 學生跟學校之間有就讀於這種關係(EX：張三就讀於某某國小)

若兩個集合X,Y裡有一個關係S，我們通常會用x~y來表示x跟y之間有關係

在關係中有一種特別的關係叫做等價關係(equivalence relation)，等價關係是同一個集合(以下將集合以X表示)之間的關係，而且必須滿足以下三種特性：

反身性Reflexive:對每個X裡面的元素x，x~x皆成立。
ex:在整數中小於這個關係並不滿足反身性，因為每個數字x<x皆不成立
而大於等於和小於等於這兩種關係皆滿足反身性，因為每個整數x>=x跟x<=x皆會成立

對稱性Symmetric:對每個X裡面的元素x,y，若x~y成立，則y~x成立。
ex:在整數中大於這個關係並不滿足對稱性，因為若是x>y，則y>x必定不會成立。
而絕對值相等這個關係會滿足對稱性，因為|x|=|y|的話，|y|=|x|也會成立
一個常常會有人誤會的地方要注意：大於等於並不會滿足對稱性
對稱性是要把所有兩個元素間的關係都要成立，即使3>=3這個數字倒過來會成立，只要有兩個元素之間的關係不成立(4>=2成立，2>=4不成立)，就不滿足對稱性。

遞移性Transitive:對每個X裡面的元素x,y,z，若x~y和y~z皆成立，則x~z成立。
ex:整數中大於有遞移性，若x>y,y>z，則x>z
但是多1這個關係沒有遞移性，因為x=y+1,y=z+1，並不會讓x=z+1成立

在等價關係中最簡單的例子是等於
他滿足了對稱性(x=x)、反身性(若x=y則y=x)和遞移性(若x=y且y=z則x=z)
之前聽到有學弟表示等於剛好滿足等價關係的條件，我認為並不是這樣
我認為應該是數學家去尋找等於這個關係滿足了什麼條件，然後將這些特性列出來去撿查其他的關係，若是跟等於有相同的特性，我們就叫他等價關係

之後如果有空我再來談談其他特別的relation

2015年6月27日星期六

[Java]如何列出100以下的所有質數

程式語言另一個常見的作業就是跟質數當朋友
來找找一個數是不是質數，或找出100以內所有的質數這種題目

今天談談怎麼找出1到100的所有質數吧
解決這個問題前先處理下面兩個問題
如何印出2到100(最小的質數是2)，答案我想剛學過迴圈的應該都做的出來，就是

  for(int i=2;i<=100;i++){
   System.out.println(i);
  }

接下來只要把1到100每個數都檢查他是不是質數就可以了，如何檢查一個整數不是質數呢
首先質數的定義是大於一的整數，除了1跟自己本身以外，沒有其他因數。
所以呢最簡單的想法就是設一個boolean去處理他
舉個例子好了，檢查7是否為質數

  boolean isPrime;
  for(int i=2;i<7;i++){

   if(7%i==0){
    isPrime=false;
   
   }
  }

所以這個迴圈就會檢查二以上，比7小的數字有沒有整除他，有整除表示7有其他因數就不是質數囉，當然最後因為2到6並不會整除7，最後isPrime的值就會是true，所以就可以抓出7是質數。

有了上述兩件事我們就可以開始把兩個程式合併起來

  boolean isPrime;
  
  for(int i=2;i<=100;i++){
   isPrime=true;
   
   for(int j=2;j<i;j++){

    if(i%j==0){
     isPrime=false;
    
    }
   }
   
   if(isPrime){
    System.out.print(i+" ");
    
   }
   
  }

 }

注意兩個迴圈不太一樣，第一個迴圈是<=100，因為你檢查的時候要檢查的是2到100
但是第二個迴圈要檢查的時候不能檢查自己，因為自己一定被自己整除，
弄成小於等於的話不管怎樣isPrime一定會false，那些該用小於等於，那些東西該用小於;，必須想的很清楚，不然程式就會花式秀bug，你還不知道怎麼死的

做到這看似完成了，但是其實這個方法從2檢查到100大概要做快5000次
(第二個for迴圈執行了4851次)
並不是很有效率，事實上你檢查的時候如果不是質數並不會用繼續檢查其他數字，可以將迴圈做break跳出，另外，在數學的觀點來講，X這個整數如果你檢查到根號X都沒有質因數，他就是質數了，故程式碼可以改成

  boolean isPrime;
  
  for(int i=2;i<=100;i++){
   isPrime=true;
   
   for(int j=2;j<Math.sqrt(i);j++){

    if(i%j==0){
     isPrime=false;
     break;
    }
   }
   
   if(isPrime){
    System.out.print(i+" ");
    
   }
   
  }

到了這邊第二個for迴圈的進入次數就被壓縮到剩下232次，應該可以感受到用不同的方法去實做程式，不去想辦法降低程式運算次數，只靠靠硬體硬做效能會有多大的差距了。
我解出上述答案後過了幾天我就在思考，如果我只檢查比根號x小的所有質數，會不會更快呢？於是我寫出了下面的class

public class ShowPrime {



 public static void main(String[] args) {

  showPrime(100); 

 

 }



 



 

 public static void showPrime(int k){

  int[] prime = new int[(k+1)/2];  

  prime[0] = 2;//the first prime is 2

  int pCount=0;

  int count=0;

  boolean isPrime=true;

  for(int i=2;i<=k;i++){

   

   isPrime=true;

   for(int j=0;prime[j]<=Math.sqrt(i);j++){

    

    if(i%prime[j]==0){

     isPrime=false;

     break;

    }

   }

   if(isPrime){

    prime[pCount]=i;

    pCount++;

    System.out.print(i+"\t");

    count++;

    if(count%10==0){//create new line per 10 numbers

     System.out.println("");

    }

      

   }

     

  }

  

 }

 

}

這邊會另外需要記憶體去儲存質數，所以在100的時候我不覺得這個方法會比較好，但是在數字更大的時候這個方法執行效能應該就會比較好了

最後提一下，我認為這邊的方法並不是最快速的方法，但是初學程式的新手最需要學習的概念，並不是只是程式語法本身，語法很重要，不去學會你完全不能開始寫程式，但是解決問題的方法也是另一個重要課題，學習如何依照使用者的要求，去找出解決問題的方案，並且找出解決方案後，去思考能不能改善他的效能，所以這個問題除了把答案解出來以外，試著去思考如何撿少運算次數一定有幫助的

2015年6月26日星期五

[Java]如何撰寫X的Y次方函數

初學JAVA不到一個月就有同學在問這個問題

然後呢過一陣子在網路上又連續遇到兩個人在問這個問題

其實這個方法在Math類別裡面有一個函數可以處理
不過通常這個題目是為了訓練初學者使用迴圈跟建立方法的訓練
雖然整數的整數次方可以簡單的用迴圈處理，可是如果輸入的參數是double就可能還要處理浮點數不精確的問題，難度就會大幅提升了

所以這邊只列出整數的整數次方
我將程式碼以及測試碼一起打在下面

public class demo {



        public static void main(String[] args) {

  //使用自己建的函數

                System.out.println(power(3,2));//3的2次方

                System.out.println(power(2,5));

  //使用java內建函數

                System.out.println(Math.pow(3, 2));

                System.out.println(Math.pow(2, 5));



        }



        public static double power(int x,int y){



                double result = 1;



                if(y>=1){



                        for(int i=0;i<y;i++){



                                result = result *x;

                        }



                }else {



                        for(int i=0;i>y;i--){



                                result = result /x;



                        }

                }

                return result;

        }



}

訂閱：文章 (Atom)


	<html>
	<head lang="zh-tw">
	<meta charset="UTF-8">
	<title>JavaScript Test</title>
	<style>

	.type{
	border:1px solid #FFC010;
	border-radius: 15px;
	width: 500px;

	}

	.title{
	width:300px;
	border-bottom:1px solid #000000;
	border:3px;
	padding:right;
	}
	.t {
	width:100px;
	float:left;
	margin: 10px;
	text-align: right;
	vertical-align:center;

	}

	</style>

	<script>


	function check(){
	if(parseInt(reg.balls.value)>=parseInt(reg.token.value)){
	takeBalls(reg.balls.value,reg.token.value);
	}else {
	window.alert("輸入的內容無法進行抽取喔~");
	}
	return undefined;
	}


	function takeBalls(balls, token){
	var result = new Array(token);

	//document.write("<div style=\"border:2px solid #FFCC00; width:400px;border-radius: 20px;text-align: center; \">")
	document.getElementById("resultset").innerHTML = '<p style="color:#00DDAA">抽取結果如下</p>';
	//document.write("<p style=\"color:#00DDAA\">抽取結果如下</p>");
	for(var i=0;i<token;i++){
	result[i]=parseInt(Math.random()*balls+1);
	for(var j=0;j<i;j++){
	if(result[j]==result[i]){
	i--;
	}
	}
	}
	result.sort(sortNumber);
	for (var i = 0; i < token; i++) {
	var OriginalFont = document.getElementById("resultset").innerHTML;
	document.getElementById("resultset").innerHTML = OriginalFont + '<span style="color:#3377FF ">' + result[i] + '號</sapn>';
	//document.write("<span style=\"color:#3377FF \">"+result[i]+"號</sapn>");
	}

	//document.write("<br><a href=\"js.html\">返回</a></div>");

	return undefined;
	}
	function sortNumber(a,b)
	{
	return a - b;
	}

	</script>


	</head>

	<body>



	<form action="#" method="post" name="reg">
	<fieldset class="type">
	<legend>樂透抽取程式</legend>
	<div class="title">
	<label class="t">總共號碼數</label><input type="number" name="balls" min="1" required="required">
	</div>
	<br>
	<div class="title">
	<label class="t">取球數</label><input type="number" name="token" min="1" required="required">
	</div>
	<br>


	<input type="button" value="確認" onclick="check()" >
	<input type="reset" value="清除">
	<br>
	<center id="resultset"></center>
	</fieldset>



	</form>



	</body>

	</html>

2015年6月30日 星期二