My Practice in Java Programming: January 2012

Friday, January 13, 2012

利用C語言寫出長整數2進位轉10進位

 
#include "stdio.h"
#define size 128

//sum[0]視為第0位, sum[1]第1位 依此類推
//例如若這陣列記14547，則sum[4] ~ sum[0]分別是1,4,5,4,7
int sum[size] = {0};

void Double()
{
 //就是把sum陣列這個長整數的值加倍，我的算法是自己加自己

 int i;
 int carry = 0; //代表有進位

 for (i = 0; i < size; i ++)
 {
  //i = 0 時，carry為0，因為第一位不會有進位
  //i > 0 時，carry 值為
  //當sum[i-1]+sum[i-1]加前一個carry>=10時就設為1，不是則為0
  //例如計算38+38，sum[0]的值為先算完sum[0]+sum[0]=16，
  //而16>10，所以設carry = 1及sum[0] = 16-10 = 6
  //接著sum[1]的值為sum[1]+sum[1]+carry = 3 + 3 + 1 = 7

  sum[i] = sum[i] + sum[i] + carry; 

  if (sum[i] >= 10)
  {
   //若這位數的和大於等於10，代表有進位，
   //這一位要減10，而下一位要多加1，
   carry = 1;
   sum[i] -= 10 ;
  }
  else
   carry = 0;
 }
}

void Add1()
{
 //就是把sum陣列的值 + 1，
 //例如136變137，其中sum[2] = 1, sum[1] = 3, sum[0] = 6，
 //變sum[2] = 1, sum[1] = 3, sum[0] = 7
 //或39變40，其中sum[1] = 3, sum[0] = 9，
 //變sum[1] = 4, sum[0] = 0

 int i = 0;
 int carry = 0;
 
 sum[0] ++;
 if ( sum[0] == 10)
 {
  //加1後若有進位，則只可能是10
  //於是carry為1，sum[0]值就為尾數0，
  carry = 1;
  sum[0] = 0;
 }

 //若carry不是1，則結尾加1後，就完成了加1；
 //是的話，則要從第二位起繼續加。例如99+1=100，sum[1]和sum[2]也跟著變
 while ( carry == 1)
 { 
  //遇到結尾是9, 99, 或9999...時，才會跑進這while
  i++;  //代表再走到下一位
  sum[i] ++; //表示這一位多加carry值1，所以sum[i]++
  if (sum[i] == 10)
  {
   //若還繼續進位的話，就會繼續維持carry = 1，sum[i]這位則變為9+1-10=0
   sum[i] = 0;
  }
  else
   break;  //表示沒繼續進位，也完成了這個數加1
 }

}


int main()
{
 int i;
 char str[size];
 int weisu;

 printf("請輸入二進位數字字串(例如01001)\n");
 scanf("%[0-1]", str); //也可把[0-1]改成d


 for (i = 0 ; i < size ; i++)
 {
  if (str[i] == '\0')
   break;

  Double(); //把sum陣列的值加倍

  if (str[i] == '1') 
   Add1();  //是1的話就多加1，不是的話就不用
 }


 //weisu代表sum陣列代表的數的最高位。
 //例如若輸入為11001，sum代表值就會是25 (sum[1] = 2, sum[0] = 5)，
 //而weisu 會等於 1

 weisu = size - 1; 
 
 //從size-1位開始，找到真正的weisu
 //例如sum陣列從最高位起為00...0015，
 //就從最高位起開始找，直到遇到的第一個不是0的位數時停下來
 //此處就代表sum的weisu
 while (sum[weisu] == 0 && weisu >= 0)
  weisu--;

 printf("這個二進位數字的十進位為：");

 if (weisu == -1)
  printf("0\n"); //沒有sum[-1]，但若遇到weisu = -1則sum代表的值必是0
 else
 {
  //從最高位印到第0位
  for (i = weisu; i >= 0 ; i --)
   printf("%d", sum[i]);

  printf("\n");

 }


 system("pause");
 return 0;
}

Monday, January 9, 2012

C++的getline與以strtok作字串分割

以下程式可以以getline輸入加法的字串，例如"1.1 + 2 + 3.5 + 4"，輸出為這幾個數的和。方法就是以strtok分割字串，然後以atof轉成數值，然後把值將加後，最後得到結果

 
#include "iostream"
#include "stdlib.h"
#include "string.h"
#include "stdio.h"

using namespace std;

int main()
{
 char str[256];

 cout << "請輸入加法運算字串，例如1.1 + 2 + 3.5 + 4 : \n";
 cin.getline(str, 100);

 char *delim = "+";
 char * pch;
 int i = 0, j;
 double answer = 0;
 double values[4];

 pch = strtok(str, delim);

 while (pch != NULL)
 {
  values[i] = atof(pch);
  cout << "values[i] = " << values[i] << endl;
  pch = strtok(NULL, delim);
  i++;
 }

 for ( j = 0 ; j < i ; j ++)
  answer = answer + values[j];

 cout << "這" << i << "個數的和為" << answer << endl;

 system("pause");
 return 0;
}

Sunday, January 8, 2012

以Prim's Algorithm來求最小成本擴張樹

 
 #include "stdafx.h"
#include <iostream>
#include <stdio.h>
#define INF 10000000

using namespace std;

//一個undirected graph的adjacency matrix
int adjMatrix[8][8] =
{
 {0, 300, 1000, INF, INF, INF, INF, 1700},
 {300, 0, 800, INF, INF, INF, INF, INF},
 {1000, 800, 0, 1200, INF, INF, INF, INF},
 {INF, INF, 1200, 0, 1500, 1000, INF, INF},
 {INF, INF, INF, 1500, 0, 250, INF, INF},
 {INF, INF, INF, 1000, 250, 0, 900, 1400},
 {INF, INF, INF, INF, INF, 900, 0, 1000},
 {1700, INF, INF, INF, INF, 1400, 1000, 0},
 
};

int addedVertices[8] = {0};
int addedVerticesNum = 1;       //紀錄成為spanning tree的各邊中其中一點的數目數目。第一個點為0

bool isAdded(int v)
{
 //檢驗這個點是不是已被加入spanning tree的邊中其中一個點

 for (int i = 0 ; i < addedVerticesNum; i ++)
 {
  if (addedVertices[i] == v)
   return true;
 }

 return false;
}


//紀錄會成為spanning tree的7條邊。若頂點數目是n則是n-1條邊
struct Edge
{
 int node1;
 int node2;

} edge[7];


int main(int argc, char* argv[])
{

 int p1, p2;   //紀錄被檢驗的邊的兩點
 int lowestWeight; //在下面的三層迴圈中，暫存與已被加入spanning tree的邊相連的邊中，weight最低的
 int thep1, thep2; //紀錄這一次要被加入minimum cost spanning tree的邊的兩個頂點  
  
 
 for (int i = 0 ; i < 8 ; i ++)
 { 
  lowestWeight = INF;

  for (int count = 0; count < addedVerticesNum; count++)
  {
   //從幾個已被加的點開始找
   p1 = addedVertices[count];

   for (p2 = 0; p2 < 8 ; p2++)
   {
    if ( p2 != p1 && adjMatrix[p1][p2] < lowestWeight && !isAdded(p2) )
    { 
     //這個要被加入spanninf tree的邊的兩個點不同，所以 p2 != p1
     //兩個點之間須有邊相連，所以 adjMatrix[p1][p2] < INF。
     //adjMatrix[p1][p2] < lowestWeight則是為了找出權重最低的邊
     //在加一條新的邊時，依prim的演算法必須一點是已被加入spanning tree的邊中的其中一點，另一點不是。
     //而p1 = addedVertices[count] 和 !isAdded(p2)代表p1是其中一點，p2不是

     lowestWeight = adjMatrix[p1][p2];
     thep1 = p1;
     thep2 = p2;
    } 
   }


  }
  

  if (lowestWeight < INF)
  {
   edge[addedVerticesNum - 1].node1 = thep1;
   edge[addedVerticesNum - 1].node2 = thep2;
   //thep1是新加入spanning tree的邊中，已和其中一條被加入spanning tree的邊相連的點，
   //thep2則是尚未與被加入spanning tree的邊相連的另一點

   addedVertices[addedVerticesNum] = thep2; 
   addedVerticesNum++;
  }
  else //若lowestWeight = INF，表示p1未與其他任何點相連，所以整個圖必定沒有spanning tree
   break;
   
 }
  
  
 

 if (addedVerticesNum < 8 )
  cout << "No spanning tree\n";
 else
 {
  cout << "The edges of the spanning tree are:\n";

  for (int i = 0 ; i < 7; i++ )
   cout << "edge " << edge[i].node1 << edge[i].node2 << endl;
 
 }

 //以文章最上面的圖為例，就會輸出
 //the edges of the spanning tree are:
 //edge 01
 //edge 12
 //edge 23
 //edge 35
 //edge 54
 //edge 56
 //edge 67


 system("PAUSE");
 return 0;
}

Monday, January 2, 2012

C++ 二元樹的刪除節點

#include "stdafx.h"

#include <iostream>

#include <stdlib.h>

using namespace std;

struct node

{

int data;

struct node *left; // self-reference linker

struct node *right; // self-reference linker

} *root, *tree, *t;

struct node *GetSmallest(struct node *ptr)

{

while (ptr->left != NULL)

ptr=ptr->left;

return ptr;

}

struct node *Delete(struct node *ptr, int value)

{

//從維基百科知，There are three possible cases to consider:

// 1. Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.

// 2. Deleting a node with one child: Remove the node and replace it with its child.

// 3. Deleting a node with two children: Call the node to be deleted N. Do not delete N.

// Instead, choose either its in-order successor node or its in-order predecessor node, R.

// Replace the value of N with the value of R, then delete R.

//第一和和第二種情形的刪除很容易，第種情形時的刪除，我是用「中序立即後繼節點(inorder immediate successor)」法，

//就是將欲刪除節點的右子樹最小者向上提。詳細可參閱網路上搜尋的介紹

struct node *temp;

if (ptr!= NULL)

{

////第一種情形

if (ptr->right == NULL && ptr->left == NULL)

ptr= NULL;

///////////

//第二種情形

else if (ptr->left == NULL)

ptr = ptr->right;

else if (ptr->right == NULL)

ptr = ptr->left;

//////////

else if (value > ptr->data)

ptr->right = Delete(ptr->right, value);

else if (value < ptr->data)

ptr->left = Delete(ptr->left, value);

////////

//第三種情形

else

{

temp = GetSmallest(ptr->right);

temp->left = ptr->left;

ptr = ptr->right;

}

/////////

}

else

cout << "Sorry, the input does not match any node's value in the tree.\n";

return ptr;

}

int main(int argc, char* argv[])

{

int i, key;

root = NULL;

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

{

cout << "Enter number " << i+1 << " > " ;

cin >> key;

if (root == NULL) // 插入第一個數字

{

root = new struct node;

root->data = key;

root->left = root->right = NULL;

}

else // 插入第二個以後的數字

{

tree = root;

while (tree != NULL)

{

if (key == tree->data) // 要插入的數字已經存在於樹中

{

cout << "duplicate node!";

break;

}

else if (key < tree->data) // 要插入的數字< 節點數字, 向左子樹移動

{

if (tree->left != NULL)

tree = tree->left; // 向左子樹移動

else // 沒有左子樹時, 則新增節點, 放置要插入的數字

{

t = new struct node;

t->data = key;

t->left = t->right = NULL;

tree->left = t;

break;

}

else // 要插入的數字> 節點數字, 向右子樹移動

{

if (tree->right != NULL)

tree = tree->right; // 向右子樹移動

else // 沒有右子樹時, 則新增節點, 放置要插入的數字

{

t = new struct node;

t->data = key;

t->left = t->right = NULL;

tree->right = t;

break;

}

cout << "root->left->left->data = " << root->left->left->data << endl;

Delete(root, 0);

cout << "root->left->data = " << root->left->data << endl;

if (root->left->left == NULL)

cout << "root->left->left == NULL";

//例如插入3 1 4 0 2 5 ，經Delete(root, 0)後，就會發現被刪掉了

system("pause");

return 0; // 設置中斷點, 察看樹的形狀

}

Sunday, January 1, 2012

複數的加減乘除的C++類別與程式

// Complex.cpp 

#include "StdAfx.h"
#include "Complex.h"
#include <iostream>

using namespace std;

Complex::Complex(double r, double i)
{
    real = r;
    imaginary = i;
}

Complex::~Complex(void)
{
}

void Complex::Add(Complex &c)
{

    real += c.real;
    imaginary += c.imaginary;

}


void Complex::Subtract(Complex &c)
{

    real -= c.real;
    imaginary -= c.imaginary;

}


void Complex::Multiply(Complex &c)
{
    real = real * c.real - imaginary * c.imaginary;
    imaginary = real * c.imaginary + imaginary * c.real;
}

void Complex::Divide(Complex &c)
{

    if ( c.real != 0 || c.imaginary != 0)
    {
    
        double fenmu = c.real * c.real + c.imaginary * c.imaginary;
        real = real * c.real + imaginary * c.imaginary;
        real /= fenmu;

        imaginary = imaginary * c.real - real * c.imaginary;
        imaginary / fenmu;
    }
    else
    {
        cout << "Cannot divide a number by zero.\n";
    }

}


void Complex::OutputValue()
{
    if (real == 0 && imaginary == 0)
        cout << "0\n";
    else if (real == 0)
    {
        if (imaginary > 0)
            cout << imaginary << "*i\n";
        else
            cout << -imaginary << "*i\n";
    }
    else if (imaginary == 0)
        cout << real << "\n";
    else
    {
        if (imaginary > 0)
            cout << real << " + " << imaginary << "*i\n";

        else
            cout << real << " - " << -imaginary << "*i\n";
    }
}

//Complex.h

#pragma once

class Complex
{
public:
    Complex(double = 0, double = 0);
    ~Complex(void);

    void Add(Complex &);
    void Subtract(Complex &);
    void Multiply(Complex &);
    void Divide(Complex &);

    void OutputValue();


private:
    float real;
    float imaginary;

};

// main.cpp : 
//

#include "stdafx.h"
#include <stdlib.h>
#include "Complex.h"
#include <iostream>
#include <ctype.h>
#define size 12

using namespace std;


bool IsDouble(char a[])
{
    int i;
    int pointsNum = 0;

    if ( !isdigit(a[0])  && a[0] != '-' && a[0] != '.')
        return false;

    if (a[0] == '.')
        pointsNum = 1;

    for (i = 1; i < size, a[i] != '\0' ; i ++ )
    {
        if ( !isdigit(a[i]) && a[i] != '.')
            return false;
        else if (a[i] == '.')
            pointsNum ++;
    }

    if (pointsNum <= 1 && i < 12)
        return true;

}


int _tmain(int argc, _TCHAR* argv[])
{
    char rr[size], ii[size];
    double r, i;

    cout << "Enter complex number c1.\n";
    cout << "real part: ";
    cin >> rr;

    while (!IsDouble(rr))
    {
        cout << "Sorry, please input a real number";
        cin >> rr;
    }
    
    r = atof(rr);
    
    cout << "imaginary part: ";
    cin >> ii;

    while (!IsDouble(ii))
    {    
        cout << "Sorry, please input a real number";
        cin >> ii;
    }
    
    i = atof(ii);

    Complex c1(r, i);

    //////////

    cout << "Enter complex number c2.\n";
    cout << "real part: ";
    cin >> rr;

    while (!IsDouble(rr))
    {
        cout << "Sorry, please input a real number";

        cin >> rr;
    }

    r = atof(rr);

    cout << "imaginary part: ";
    cin >> ii;

    while (!IsDouble(ii))
    {    
        cout << "Sorry, please input a real number";
        cin >> ii;
    }
    
    
    i = atof(ii);

    Complex c2(r, i);

    ///////

    Complex tempc1, tempc2;
    tempc1 = c1;
    tempc2 = c2;

    cout << "\nThe value c1 + c2 is :";
    c1.Add(c2);
    c1.OutputValue();

    /////////

    c1 = tempc1;
    c2 = tempc2;

    cout << "\nThe value c1 - c2 is :";
    c1.Subtract(c2);
    c1.OutputValue();

    /////////

    c1 = tempc1;
    c2 = tempc2;

    cout << "\nThe value c1 * c2 is :";
    c1.Multiply(c2);
    c1.OutputValue();

    /////////

    c1 = tempc1;
    c2 = tempc2;

    cout << "\nThe value c1 / c2 is :";
    c1.Divide(c2);
    c1.OutputValue();

    /////////

    c1 = tempc1;
    c2 = tempc2;

    system("pause");
    return 0;
}

C++ [泡沫排序] [ 模擬提款機]

//第一題：

// CPPTest.cpp : 定義主控台應用程式的進入點。

//

#include "stdafx.h"
#include<iomanip>
#include<iostream>
#include<stdlib.h>
#include<time.h>

using namespace std;

void BubbleSort(int num)
{

    int* ptr = new int[num];

    for (int i = 0; i < num; i ++)
    {
        cout << "Enter number " << i+1 << " > " ;

        cin >> ptr[i];
    }

    int temp;

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

    {

        for (int j = i+1; j < num ; j++)

        {

            if (ptr[i] > ptr[j])

            {

                temp = ptr[i];

                ptr[i]=ptr[j];

                ptr[j]=temp;

            }

        }

   

    }

    cout << "The sorted numbers in ascending order are: \n";

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

    {

        cout << ptr[i];

        cout << " ";

    }

}

int _tmain(int argc, _TCHAR* argv[])

{

   

    int num;

    cout << "Enter the number of inegers: ";

    cin >> num;
   
    BubbleSort(num);

    system("pause");

    return 0;

}

-----

//第二題：

// CPPTest.cpp : 定義主控台應用程式的進入點。

//

#include "stdafx.h"
#include<iomanip>
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<cstring>

#define size 15

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

    int money;

    int deposition, withdrawal;

    int choice;

    fstream file;

    while(true)

    {

        cout << "(1)Balance Check  \n";
        cout << "(2)Withdraw       \n";
        cout << "(3)Deposit      \n";
        cout << "(4)Clear      \n";
        cout << "(5)Exit      \n";
        cout << "Please choose a service: ";

        cin >> choice;

        if (choice == 1)
        {        ifstream fin("money.txt", ios::in);

                fin >> money;
                cout << "The balance in your account is : "  

                     << money << " dollars.\n\n";
        }

        else if (choice == 2)
        {

            ifstream fin("money.txt");

            fin >> money;

            cout << "Enter the amount of money you withdraw: ";

            cin >> withdrawal;

            if (withdrawal <= money)

            {

                ofstream fout("money.txt", ios::trunc);

                fout << money - withdrawal;

                cout << "The balance in your account now is : "  

                     <<  money - withdrawal << " dollars\n\n";

            }

            else
            {

                cout << "The balance in your account now is only " 

                     << money << " dollars and not enough to withdraw " 

                     << withdrawal << " dollars.\n\n";
            }

        }

        else if (choice == 3)
        {

                ifstream fin("money.txt");

                fin >> money;

                cout << "Enter the amount of money you deposit: ";

                cin >> deposition;

                ofstream fout("money.txt", ios::trunc);

                fout << money + deposition;

                cout << "The balance in your account now is : "  

                      <<  money + deposition << " dollars.\n\n";

        }

        else if (choice == 4)
        {

            ofstream fout("money.txt", ios::trunc);

            fout << 0;

            cout << "The balance in your account now is 0 dollar.\n\n";

       

        }

        else if (choice == 5 )
        {
            break;
        }

    } "pause");
    return 0;

}