[ C\C++ ] Bài toán người đưa thư sử dụng giải thuật Heuristic [ Giải thuật - Trí tuệ nhân tạo ]

1. Phát biểu bài toán:

Bài toán: Để tiết kiệm thời gian đi đưa thư trong một địa phương. Người đưa thư phải đi qua tất cả các điểm cần phát thư rồi trở về vị trí ban đầu với đường đi ngắn nhất.

Bài toán có thể phát biểu lại như sau: Giả sử có một đồ thị có trọng số dương, tìm đường đi ngắn nhất qua tất cả các đỉnh của đồ thị rồi trở về đỉnh ban đầu.

2. Hạn chế khi sử dụng thuật toán tối ưu:

Đồ thị có n đỉnh, khi đó thuật toán tối ưu cho bài toán này sẽ là thuật toán tìm đường đi ngắn nhất cho chu trình Haminton. Do đó thuật toán tối ưu sẽ có độ phức tạp là O(n!).

ĐI TÌM một thuật giải Heuristic cho bài toán này.

3. Sử dụng thuật toán Heuristic cho bài toán người đưa thư:

- Theo kinh nghiệm của con người trong thực tế thì khi ta đi trên những đoạn đường ngắn nhất thì cuối cùng ta sẽ có một hành trình ngắn nhất à sử dụng nguyên lý tham lam.

- Thuật giải bài toán sử dụng nguyên lý tham lam:


- Ví dụ về thuật giải trên:

Với một đồ thị trọng số dương như hình bên. Nếu ta xuất phát từ đỉnh sổ 1, thì đỉnh tiếp theo phải đến là 2 (vì cạnh 1-2 có trọng số nhỏ nhất so với các đỉnh chưa đến của 1), như vậy tiếp theo ta sẽ đến các đỉnh theo thứ tự là 5, 3, 4, và trở về 1.

Như vậy đường đi ngắn nhất theo giải thuật trình bày trên tìm được là: 1 + 3 + 2 + 1+ 7 = 14

4. Cài đặt thuật toán.
(ma trận trọng số, kích thước 5x5)

- Ta có dạng ma trận hóa của đồ thị trong ví dụ ở mục 3, như hình bên:

- Chương trình được viết trên môi trường Turbo C++ 3.0.

- Input: một ma trận vuông bằng file “graph.txt “ có dạng như hình bên (tài về tại đây), hay nhập ma trận bằng tay.

- Output: đường đi theo thuật giải Heuristic, và chi phí của đường đi đó.

- Tổ chức dữ liệu chương trình: (hình dưới)

Trong đó:
  + n: là biến cho biết số đỉnh của đồ thị.

  + G: dùng để trỏ tới các giá trị của ma trận.

  + v[Gr.n + 1]: dùng để lưu trữ đường đi theo thuật giải Heuristic.

  + Gr.G[ i][j ]: đồ thị dưới dạng ma trận.

  + x: là đỉnh đầu tiên xuất phát.

  + initGraph(Graph &Gr): Hàm dùng để khởi tạo một đồ thị mới từ cấu trúc đã tổ chức.

  + ReadGraph(Graph &Gr): dùng để đọc đồ thị từ file .txt

  + inputHandle( Graph &Gr): dùng để nhập đồ thị bằng tay.

  + outputGraph(Graph Gr): dùng để xuất đồ thị đã được nhập ra màn hình.

  + testGraph(int a, int* v, Graph Gr): Kiểm tra điểm đang duyệt có trùng với điểm đã duyệt trên ma trận không. Được gọi trong hàm topNear(…).


  + topNear(int a, Graph Gr, int* v) : Hàm tìm đỉnh kế tiếp theo thuật giải Heuristic. Được gọi lại trong hàm FindWay(…) .


+ FindWay(int x, Graph Gr, int* v): Hàm tìm đường đi theo giải thuật Heuristic. Dựa theo cách tìm đường đi có trọng số nhỏ nhất để đi bước tiếp theo.

- Giao diện chương trình: console Aplication.


Khi thực thi, chương trình sẽ yêu cầu chọn nhập ma trận đồ thị bằng tay hay bằng file “graph.txt”. Ví dụ như hình trên chọn nhập ma trận bằng file txt. Ta nhập tiếp đỉnh bắt đầu (ở đây nhập 1), thì chương trình sẽ cho ra đáp án cho ví dụ trên:

=> Đường đi là: 1 – 2 – 5 – 3 – 4 – 1

=> Chi phí cho đường đi này theo giải thuật Heuristic là: 14.

Nếu như chọn cách nhập ma trận bằng tay thì ta phải nhập từng giá trị của ma trận vào.

- Nhấn ESC để thoát khỏi chương trình, Phím bất kỳ để tiếp tục chương trình với cách duyệt từ đỉnh khác.[Tài toàn bộ code chương trình - Turbo C++ tại đây]

5. Đánh giá thuật giải Heuristic của bài toán:

* Ưu điểm: Thuật giải Heuristic cho bài toán người đưa thư có độ phức tạp O(n2 ) tốt hơn rất nhiều so với thuật toán tối ưu (có độ phức tạp O( n!) ).

* Nhược điểm: thuật giải có những hạn chế, chưa cho ra lời giải chính xác.

>> Kết luận: Thuật giải Heuristic cho bài toán người đưa thư tuy chưa đưa ra được lời giải chính xác cho bài toán, nhưng nó cho ra một lời giải có thể chấp nhận được với độ phức tạp thấp hơn nhiều so với thuật toán tối ưu.

>>> Tải code chương trình tại đây.
Lưu ý: 
  - Sau 5s, click BỎ QUA QUẢNG CÁO (SKIP AD)
  - File grapt.txt đặt tại cùng thư mục với code chương trình.

Nguồn: thanhcuong

[ Lập trình Android ] Ví dụ: Xây dựng ứng dụng MÁY TÍNH ĐIỆN TỬ [ ứng dụng Android cơ bản ]

Xây dựng ứng dụng mô phỏng máy tính điện tử đơn giản trên Android:


Để xây dựng ứng dụng trên, chúng ta tiến hành như sau (Cài đặt trên môi trường Eclipse đã plugin SDK, xem thêm tại đây):

Bước 1: Tạo Project Vidu1 với các thành phần như hình vẽ


 Bước 2: Viết nội dung các file:  PhepTinh.java (chứa các xử lý tính toán); Vidu1.Activity.java (file chạy Android); main.xml (thiết kế giao diện); color.xml (thiết lập màu sắc); string.xml (thiết lập các giá trị cho string). Nội dung cụ thể:

+ color.xml

<?xml version="1.0" encoding="utf-8"?>
<resources>
<color name="title_color">#0000FF</color>
<color name="text_color">#DC143C</color>
<color name="resul_color">#FFD700</color>
<color name="backg_color">#F0F8FF</color>
<color name="btn_color">#FF0000</color>

</resources>

+ string.xml

<?xml version="1.0" encoding="utf-8"?>
<resources>
    <string name="str1">MÁY TÍNH ĐIỆN TỬ</string>
    <string name="app_name">Vd1</string>
    <string name="a">a: </string>
    <string name="b">b: </string>
    <string name="kq">Kết quả: </string>
    <string name="cong">+</string>
    <string name="tru">-</string>
    <string name="nhan">x</string>
    <string name="chia">/</string>
    <string name="xoa">Xóa</string>
    <string name="thoat">Thoát</string>
    <string name="tb1">Nhập số thứ nhất</string>
    <string name="tb2">Nhập số thứ hai</string>
     <string name="chao">http://lap-trinh-may-tinh.blogspot.com</string>
</resources>

+ main.xml

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="fill_parent"
    android:layout_height="fill_parent"
    android:orientation ="vertical"
    android:background="@color/backg_color"
    >
   
       
   <TextView
     android:layout_width="wrap_content"
     android:layout_height="wrap_content"     
     android:textColor="@color/title_color"
     android:text="@string/str1"       
     android:textSize="30dp"
     />

   
   <LinearLayout
       android:layout_width="wrap_content"
       android:layout_height="wrap_content"
       android:orientation="horizontal"
       >
       
   <TextView
     android:layout_width="wrap_content"
     android:layout_height="wrap_content"     
     android:textColor="@color/text_color"
     android:text="@string/a"       
     android:textSize="30dp"
     />
   
   <EditText
android:layout_width="200dp"
     android:layout_height="50dp"
     android:textColor="@color/text_color"
     android:id="@+id/so1"
android:hint="@string/tb1"
              
   />
   
   </LinearLayout>
   
   <LinearLayout
       android:layout_width="wrap_content"
       android:layout_height="wrap_content"
       android:orientation="horizontal"
       >
   <TextView
     android:layout_width="wrap_content"
     android:layout_height="wrap_content"
     android:textColor="@color/text_color"
     android:text="@string/b"       
     android:textSize="30dp"
     />
    <EditText
android:layout_width="200dp"
     android:layout_height="50dp"
     android:textColor="@color/text_color"
     android:id="@+id/so2"
android:hint="@string/tb2"
              
   />
   
   </LinearLayout>
   
   <LinearLayout
       android:layout_width="wrap_content"
       android:layout_height="wrap_content"
       android:orientation="horizontal"
       >
   <TextView
     android:layout_width="wrap_content"
     android:layout_height="wrap_content"
     android:textColor="@color/resul_color"
     android:text="@string/kq"       
     android:textSize="30dp"
     />
   <EditText
android:layout_width="200dp"
     android:layout_height="50dp"
     android:textColor="@color/resul_color"
     android:id="@+id/ketqua"              
   />   
   </LinearLayout>
<LinearLayout
    android:layout_width="wrap_content"
    android:layout_height="wrap_content"
    android:orientation="horizontal">
 <Button   
     android:layout_width="80dp"
     android:layout_height="40dp"
     android:text="@string/cong"
     android:textColor="@color/btn_color"
     android:id="@+id/phepCong"
    />
    <Button   
     android:layout_width="80dp"
     android:layout_height="40dp"
     android:text="@string/tru"
     android:textColor="@color/btn_color"
     android:id="@+id/phepTru"
    />
    <Button   
     android:layout_width="80dp"
     android:layout_height="40dp"
     android:text="@string/nhan"
     android:textColor="@color/btn_color"
     android:id="@+id/phepNhan"
    />
    <Button   
     android:layout_width="80dp"
     android:layout_height="40dp"
     android:text="@string/chia"
     android:textColor="@color/btn_color"
     android:id="@+id/phepChia"
    />
 </LinearLayout>
<LinearLayout
    android:layout_width="wrap_content"
    android:layout_height="wrap_content"
    android:orientation="horizontal">
 <Button   
     android:layout_width="80dp"
     android:layout_height="40dp"
     android:text="@string/xoa"
     android:textColor="@color/btn_color"
     android:id="@+id/delete"
    />
    <Button   
     android:layout_width="80dp"
     android:layout_height="40dp"
     android:text="@string/thoat"
     android:textColor="@color/btn_color"
     android:id="@+id/cancel"
    />
 </LinearLayout>
<LinearLayout
    android:layout_width="wrap_content"
    android:layout_height="wrap_content"
    android:orientation="horizontal">
  <TextView
     android:layout_width="wrap_content"
     android:layout_height="wrap_content"     
     android:textColor="@color/text_color"
     android:text="@string/chao"       
     android:textSize="12dp"
     />
 </LinearLayout>

</LinearLayout>

+ PhepTinh.java:

package txt.vidu1.vidu;

public class PhepTinh {
 public float a,b;
 // khoi tao
 public PhepTinh(float a,float b){
this.a=a;this.b=b;
 }
 // tinh tong
 public float Tong(){
return a+b;
 }
 // tinh hieu
 public float Hieu(){
return a-b;
 }
 public float Nhan(){
return a*b;
 }
 public float Chia(){
if (b==0)
return 0;
return a/b;
 
 }
}

Vidu1.Activity.java

package txt.vidu1.vidu;

import android.app.Activity;
import android.app.AlertDialog;
import android.content.DialogInterface;
import android.os.Bundle;
import android.view.View;
import android.widget.Button;
import android.widget.EditText;
import android.widget.TextView;

public class Vidu1Activity extends Activity {
    
    protected AlertDialog AlertDialog;

@Override
    public void onCreate(Bundle savedInstanceState) {
        
    super.onCreate(savedInstanceState);
        
        setContentView(R.layout.main);
        // khai bao cac button
        final Button btnCong= (Button) findViewById(R.id.phepCong);
        final Button btnTru=(Button) findViewById(R.id.phepTru);
        final Button btnNhan=(Button) findViewById(R.id.phepNhan);
        final Button btnChia=(Button) findViewById(R.id.phepChia);
        final Button btnXoa=(Button) findViewById(R.id.delete);
        final Button btnThoat=(Button) findViewById(R.id.cancel);
        // khai bao textView
        final TextView txvKQ=(TextView) findViewById(R.id.ketqua);
        
        // Su kien click Phep Cong
        btnCong.setOnClickListener(new Button.OnClickListener() {
        public void onClick(View v) {
         float a= Float.valueOf(((EditText) findViewById(R.id.so1)).getText().toString());
         float b= Float.valueOf(((EditText) findViewById(R.id.so2)).getText().toString());
         PhepTinh c=new PhepTinh(a,b);
         String s=String.valueOf(c.Tong());
         txvKQ.setText(s);
        }                
        });
        // Su kien click Phep tru
        btnTru.setOnClickListener(new Button.OnClickListener() {
          public void onClick(View v){
         float a,b;
         a=Float.valueOf(((EditText) findViewById(R.id.so1)).getText().toString());
         b=Float.valueOf(((EditText) findViewById(R.id.so2)).getText().toString());
         PhepTinh t=new PhepTinh(a,b);
         txvKQ.setText(String.valueOf(t.Hieu()));          
          }
        }        
        );
        // Su kien click Phep nhan
        btnNhan.setOnClickListener(new Button.OnClickListener(){
        public void onClick(View v){
        float a,b;
        a=Float.valueOf(((EditText) findViewById(R.id.so1)).getText().toString());
        b=Float.valueOf(((EditText) findViewById(R.id.so2)).getText().toString());
        PhepTinh n=new PhepTinh(a,b);
        txvKQ.setText(String.valueOf(n.Nhan()));
        }
        }
       
        );
        
        // Su kien click Phep chia       
        btnChia.setOnClickListener(new Button.OnClickListener(){
        public void onClick(View v){
        float a,b;
        a=Float.valueOf(((EditText) findViewById(R.id.so1)).getText().toString());
        b=Float.valueOf(((EditText) findViewById(R.id.so2)).getText().toString());
        PhepTinh m=new PhepTinh(a,b);
        txvKQ.setText(String.valueOf(m.Chia()));
        }
        }
       
        );
        // Su kien click Xoa
        btnXoa.setOnClickListener(new Button.OnClickListener(){
        public void onClick(View v){
        final EditText edtSo1 = (EditText) findViewById(R.id.so1);
        edtSo1.setText("");
        final EditText edtSo2 = (EditText) findViewById(R.id.so2);
        edtSo2.setText("");
        txvKQ.setText("");
       
        }
        }        
        );
        // su kien click Thoat
        btnThoat.setOnClickListener(new Button.OnClickListener(){
        public void onClick(View v){
        AlertDialog.Builder atd = new AlertDialog.Builder(Vidu1Activity.this);
        atd.setTitle("Thong bao");
        atd.setMessage("Bạn muốn thoát ?");
        atd.setPositiveButton("Đồng ý", new DialogInterface.OnClickListener() {
        public void onClick(DialogInterface dialog, int which) {
        finish();        
        }
        });
        atd.show();
        }
        }        
        );
    }

}

[ C# ] Làm việc với File và Directory trong C#

.NET Framework của Microsoft cung cấp cho chúng ta namespace System.IO để làm việc với thư mục và tập tin trên máy tính. Bài viết sau đây sẽ hướng dẫn các bạn một số phương thức và lớp rất hữu dụng khi thao tác với tập tin/thư mục.

Trong tất cả các đoạn code sau này, chúng ta lưu ý đều phải có chỉ dẫn tham chiếu đến System.IO như sau ở đầu:

using System.IO;

Lấy thông tin về File, Directory hoặc Drive

Thông qua các lớp FileInfo, DirectoryInfo và DriveInfo, chúng ta có thể lấy được thông tin về đối tượng như: ngày khởi tạo, kích thước, phần mở rộng, thuộc tính… Ví dụ sau đây cho phép chúng ta nhập vào đường dẫn đến một tập tin và sẽ hiển thị thông tin về tập tin, thư mục cha và ổ đĩa chứa tập tin đó.

using System; 
using System.Collections.Generic; 
using System.IO; 
namespace Example 
  class Test 
   { 
     public static void Main() 
      { 
        Console.Write("Enter file path:"); 
        string filePath = Console.ReadLine(); 
        Console.WriteLine("File Information"); 
        FileInfo fileInfo = new FileInfo(filePath); 
        if (fileInfo.Exists) 
          { 
             Console.WriteLine("Creation Time: " + fileInfo.CreationTime.ToString()); 
             Console.WriteLine("Last Access Time: " + fileInfo.LastAccessTime.ToString());                           
             Console.WriteLine("File Length (bytes): " + fileInfo.Length.ToString()); 
             Console.WriteLine("File Attributes: " + fileInfo.Attributes.ToString()); 
        } Console.WriteLine();   
           Console.WriteLine("Directory Information"); 
           DirectoryInfo directoryInfo = fileInfo.Directory; 
           if (directoryInfo.Exists) 
            { 
               Console.WriteLine("Creation Time: " + directoryInfo.CreationTime.ToString());             
               Console.WriteLine("Last Access Time: " + directoryInfo.LastAccessTime.ToString());    
               Console.WriteLine("Directory contains: " + directoryInfo.GetFiles().Length.ToString() + " files"); 
           } Console.WriteLine(); 
              Console.WriteLine("Drive Information"); 
              DriveInfo driveInfo = new DriveInfo(fileInfo.FullName); 
              if (driveInfo.IsReady) 
                 { 
                    Console.WriteLine("Drive Name: " + driveInfo.Name); 
                    Console.WriteLine("Drive Type: " + driveInfo.DriveType.ToString());          
                    Console.WriteLine("Drive Format: " + driveInfo.DriveFormat.ToString());
                    Console.WriteLine("Drive Free Space: " + driveInfo.AvailableFreeSpace.ToString()); 
                  } Console.ReadKey(); 
           } 
       } 
   }

Đầu tiên, chúng ta sẽ yêu cầu người dùng nhập vào đường dẫn đến một tập tin bất kỳ trên máy tính. Dựa trên đường dẫn này, chúng ta sẽ tạo ra đối tượng FileInfo để lấy thông tin về tập tin
Console.Write("Enter file path:"); 
string filePath = Console.ReadLine(); 
FileInfo fileInfo = new FileInfo(filePath);

Điều mà trước hết phải làm là kiểm tra xem thử tập tin này có thực sự tồn tại hay không. Lưu ý là mặc dù đường dẫn của chúng ta có đúng hay sai thì đối tượng fileInfo vẫn sẽ được tạo ra (không bao giờ NULL). Chúng ta sẽ dựa vào thuộc tính Exists để kiểm tra xem tập tin đó có tồn tại hay không. Sau khi đã kiểm tra được chắn chắn là tập tin này tồn tại, chúng ta lấy ra các thông tin về tập tin đó bao gồm: Thời gian khởi tạo, Thời gian truy cập cuối cùng, Thuộc tính và Kích thước của tập tin. Ngoài ra, chúng ta còn có thể lấy được các thông tin khác từ đối tượng FileInfo cũng như nhiều phương thức có thể được gọi từ lớp này (chi tiết xem tại MSDN: FileInfo)

Việc tiếp theo là chúng ta in ra thông tin thư mục chứa tập tin đã chỉ định. Thuộc tính Directory của fileInfo sẽ trả về một đối tượng DirectoryInfo của thư mục cha, dựa trên đối tượng này, chúng ta có thể lấy ra thông tin của thư mục tương tự như thông tin của tập tin:

DirectoryInfo directoryInfo = fileInfo.Directory; 
if (directoryInfo.Exists) 
 { 
   Console.WriteLine("Creation Time: " + directoryInfo.CreationTime.ToString()); 
   Console.WriteLine("Last Access Time: " + directoryInfo.LastAccessTime.ToString()); 
   Console.WriteLine("Directory contains: " + directoryInfo.GetFiles().Length.ToString() + " files"); 
}

Cuối cùng, chúng ta lấy thông tin về ổ đĩa chứa tập tin đã chỉ định. Lưu ý rằng đối tượng FileInfo không có thuộc tính nào để trả về đối tượng DriveInfo của ổ đĩa chứa nó, do đó chúng ta sẽ phải tạo ra một đối tượng DriveInfo bằng cách truyền vào hàm khởi tạo của nó một đường dẫn hợp lệ bắt đầu từ ổ đĩa đó. Sau đó, chúng ta phải kiểm tra thuộc tính IsReady của ổ đĩa này nhằm chắc chắn rằng nó thực sự tồn tại (ví dụ trong trường hợp chúng ta lấy về thông tin ổ đĩa DVD mà lại chưa bỏ đĩa vào thì chắc chắn IsReady của nó bằng False)

DriveInfo driveInfo = new DriveInfo(fileInfo.FullName); 
if (driveInfo.IsReady) 
 { 
   Console.WriteLine("Drive Name: " + driveInfo.Name); 
   Console.WriteLine("Drive Type: " + driveInfo.DriveType.ToString()); 
   Console.WriteLine("Drive Format: " + driveInfo.DriveFormat.ToString()); 
   Console.WriteLine("Drive Free Space: " + driveInfo.AvailableFreeSpace.ToString()); 
}

Sao chép, di chuyển và xóa tập tin hoặc thư mục

Dựa trên các đối tượng FileInfo và DriveInfo đã tạo ra ở trên mà chúng ta có thể gọi các phương thức để thực hiện việc Sao chép, di chuyển và xóa tập tin/thư mục. Các phương thức quan trọng của các lớp FileInfo là:
CopyTo: Sao chép tập tin đến đường dẫn được chỉ định và trả về đối tượng FileInfo của tập tin vừa được sao chép. Ví dụ sao chép tập tin đến ổ C: fileInfo.CopyTo(@“C:\” + fileInfo.Name); (các bạn lưu ý kí tự @ trước chuỗi để khỏi phải gõ ký tự \ hai lần.
Delete: Xóa tập tin vĩnh viễn nếu nó thực sự tồn tại. Lưu ý rằng phương thức này sẽ xóa trực tiếp tập tin vĩnh viễn chứ không phải là di chuyển tập tin đó đến thùng rác. Phiên bản hiện tại của C# không có cung cấp phương thức nào để chúng ta di chuyển tập tin đến thùng rác mà chúng ta cần phải tham chiếu đến thư viện của Visual Basic. Xem thêm tại:Delete File to Recycle Bin in C#
MoveTo: Di chuyển tập tin này đến vị trí mới. Phương thức này cũng được dùng để đổi tên một tập tin mà không thay đổi đường dẫn của nó. Ví dụ di chuyển tập tin đến ổ C: fileInfo.MoveTo(@”C:\” + fileInfo.Name);
Replace: Thay thế nội dung của tập tin nào đó được chỉ định bằng nội dung của tập tin chứa trong đối tượng FileInfo
Đối với thư mục thì chúng ta có các phương thức sau đây nằm trong lớpDirectoryInfo:
Create: Tạo ra một thư mục mới từ đối tượng DirectoryInfo
CreateSubdirectory: Tạo ra thư mục con chứa trong đường dẫn được chỉ định
Delete: Xóa thư mục
MoveTo: Di chuyển thư mục (kể cả nội dung bên trong) đến đường dẫn mới nằm trên cùng một ổ đĩa. Phương thức MoveTo cũng được dùng để đổi tên thư mục.
Làm việc với các lớp Path, File và Directory

Lớp Path cung cấp cho chúng ta các phương thức tĩnh tiện ích nhằm thao tác với đường dẫn của tập tin hoặc thư mục. Một vài phương thức phổ biến trong Path là:

Combine: Kết hợp một mảng các đường dẫn với nhau và trả về một đường dẫn duy nhất. 
Ví dụ: Path.Combine(@”C:\abc\”, @”efg\file.txt”); sẽ trả về C:\abc\efg\file.txt
 
GetDirectoryName: Trả về đường dẫn đến thư mục chứa tập tin trong đường dẫn đó. 
Ví dụ:Path.GetDirectoryName(@”C:\abc\file.txt”) sẽ trả về chuỗi C:\abc
GetExtension: Trả về phần mở rộng của tập tin được chỉ định. Ví dụ:Path.GetExtension(“Download.rar”) sẽ trả về chuỗi “.rar”
GetFileName: Lấy tên của tập tin từ đường dẫn được chỉ định. Tên tập tin được trả về sẽ bao gồm cả phần mở rộng. Nếu chỉ muốn lấy tên không thôi thì sử dụng phương thức GetFileNameWithoutExtension
GetFullPath: Trả về đường dẫn đầy đủ đến tập tin được chỉ định. Đường dẫn này sẽ dựa trên thư mục hiện tại của ứng dụng chạy. Ngoài ra, lớp Path còn có các phương thức tiện ích khác hỗ trợ rất nhiều khi lập trình, chi tiết xem tại: MSDN: Path class
Lớp File và Directory được dùng để thao tác trên tập tin và thư mục tương tự như lớp FileInfo và DirectoryInfo. Tuy nhiên, điểm khác biệt là chúng ta sẽ thao tác chủ yếu qua các đường dẫn đến tập tin/thư mục chứ không cần phải tạo ra một đối tượng FileInfo hoặc DirectoryInfo. 

Một số ví dụ:
//Sao chép tập tin:  
  File.Copy(@"C:\abc.txt", @"F:\Temp\test.txt"); 
//Xóa tập tin:  
  File.Delete(@"C:\abc.txt"); 
//Di chuyển tập tin:  
  File.Move(@"C:\abc.txt", @"F:\Temp\test.txt");
//trả về mảng chuỗi các tập tin trong thư mục MyFolder của ổ đĩa C: 
  Directory.GetFiles(@"C:\MyFolder\");

Các bạn có thể xem thêm tại MSDN: File classDirectory class

Tổng kết:
Trong bài hôm nay, chúng ta đã tìm hiểu qua về cách thức lấy thông tin từ tập tin, thư mục và ổ đĩa cũng như một số thao tác cơ bản như Sao chép, Di chuyển, Xóa. Chúng ta cũng đã tìm hiểu qua về những phương thức tĩnh trong các lớp Path, File và Directory để làm việc dựa trên các đường dẫn đến tập tin và thư mục. Có một lưu ý khi các bạn làm việc với các tập tin, thư mục là chúng ta cần phải quan tâm đến quyền truy nhập đến tập tin/thư mục đó là như thế nào để chắc chắn ứng dụng của chúng ta hoạt động bình thường trên các máy tính khác nhau. Trong bài tiếp theo, chúng ta sẽ tìm hiểu làm thế nào để tạo một cây thư mục như trong Windows Explorer bằng TreeView.

Nguồn: Chienuit

[ C\C++ ] Chuyển đổi từ số thực sang chuỗi kí tự trong C/C++

Như ta đã biết, trong C/C++ có tích hợp một số các hàm chuyển đổi cho phép ta chuyển đổi qua lại giữa các loại dữ liệu. 

Một số hàm thường dùng:
 - atoi (chuyển chuỗi sang số nguyên), 
 - atof (chuyển sang float), 
 - atol (chuyển sang số longint), ...
các hàm này có trong thư viện stdlib.h

Và ngược lại, từ số nguyên ta có thể chuyển đổi về chuỗi một cách dễ dàng dùng hàm itoa(). 



Ví dụ [code C]:
#include <stdlib.h> // for itoa() call
#include <stdio.h> // for printf() call
int main()
{
  int num = 123;
  char buf[5];
// convert 123 to string [buf]
  itoa(num, buf, 10);
// print our string
  printf("%sn", buf);
  return 0;
}

Lưu ý cần đảm bảo buf đủ chỗ chứa số cần chuyển để tránh trường hợp tràn bộ đệm, kích thước cỡ (sizeof(int)*8 + 1).

Chuyển đổi đối với số nguyên là như vậy nhưng đôi khi ta lại gặp trường hợp khó hơn là chuyển đổi float sang chuỗi vì trong thư viện của C/C++ không có hàm nào cho phép ta làm việc này. Thật may mắn, như các bạn biết trong câu lệnh printf() chúng ta khi in ra màn hình có thể ép kiểu các loại dữ liệu để cho ra kết quả đúng như ý muốn. Tương tự như vậy, chúng ta có thể sử dụng hàm sprintf() để chuyển đổi. Hàm này tương tự như hàm printf() nhưng thay vì in ra màn hình thì hàm này đưa vào trong bộ đệm để lưu trữ. Từ đó ta có thể dủng một chuỗi để chứa bộ đệm này. 

Cú pháp hàm này như sau: sprintf(string, “formatting string”, vars). 
Bây giờ hãy xét một ví dụ cụ thể

#include <stdio.h>
int main()
 {
   float pi = 3.141596;
   char halfpie[80];
   pi/=2;
   sprintf(halfpie, "%f", pi);
   printf("Here is the result: %sn", halfpie);
   return 0;
}


Tuy nhiên còn vấn đề ở đây!!

Hàm sprintf() tỏ ra không an toàn vì không có kiểm tra giới hạn của bộ đệm, và hoàn toàn bộ đệm có thể bị tràn và một số vấn đề khác,...

Thay vì dùng hàm sprintf(), chúng ta sử dụng hàm snprintf() , trong đó n chính là giới hạn thông tin bạn đưa vào trong bộ đệm. 

Cú pháp: snprintf(string, size, “format string” , vars)

Hàm snprintf() chỉ cho phép nạp size kí tự vào trong bộ nhớ. 

Ví dụ cụ thể: 

#include <stdio.h> 
int main()
{
  float pi = 3.141596;
  char halfpie[80];
  pi/=2;
  snprintf(halfpie, 79, "%f", pi);
  printf("Here is the result: %sn", halfpie);
  return 0;
}

>>> Download Turbo C\C++ tại đây
Nguồn: Chienuit

[Thuật toán đồ thị / code C++] Thuật toán Dijkstra - tìm đường đi ngắn nhất từ đỉnh D đến đỉnh C trên đồ thị G.

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định đường đi ngắn nhất từ đỉnh D tới đỉnh C của đồ thị G.

Ý tưởng thuật toán: sử dụng thuật toán Dijkstra (tìm hiểu thêm về thuật toán Dijkstra tại đây).

Mô tả dữ liệu đầu vào và đầu ra của bài toán:

+ Dữ liệu vào: đồ thị đã liên thông và cho trong tập tin Dijkstra.inp.
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
- Dòng thứ hai lưu đỉnh D và đỉnh C.
- Dòng i+2 (1 <= i <= n ) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.

+ Dữ liệu ra: xuất ra màn hình đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được.




[Cài đặt thuật toán với Turbo C++]

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define max 100
#define FileIn "Dijkstra.inp"

// doc file chua do thi G
void Doc_File(int A[max][max], int &n, int &D, int &C) {
  FILE*f = fopen(FileIn,"rb");
  fscanf(f,"%d%d%d",&n,&D,&C);
  cout<<"Ma Tran Lien Ket Tuong Ung.\n";
  cout<<D<<" "<<C<<endl;
  for(int i =0;i<n;i++) {
    for(int j =0;j<n;j++) {
       fscanf(f,"%d",&A[i][j]);
       cout<<A[i][j]<<" ";
    }
   cout<<endl;
  }
  fclose(f);
  D--; C--;
 }

// thuat toan Dijkstra
void Dijkstra(int A[max][max], int n, int D, int C) {
  char DanhDau[max];
  int Nhan[max], Truoc[max], XP, min;
  for(int i=0; i<n; i++){
  Nhan[i] = MAXINT;
  DanhDau[i] = 0;
  Truoc[i] = D;
 }
 Nhan[D] = 0;
 DanhDau[D] = 1;
 XP = D;
 while(XP != C){
    for(int j=0; j<n; j++)
       if(A[XP][j]>0 && Nhan[j]>A[XP][j]+Nhan[XP] && DanhDau[j]==0) {
          Nhan[j] = A[XP][j]+Nhan[XP];
          Truoc[j] = XP;
       }
       min = MAXINT;
       for(j = 0; j<n; j++)
         if(min>Nhan[j]&& DanhDau[j]==0){
            min = Nhan[j];
           XP = j;
        }
      DanhDau[XP] = 1;
  }
  cout<<"Duong Di Ngan Nhat La:"<<Nhan[C]<<endl;
  cout<<C+1<<" <- "<<Truoc[C]+1;
  i = Truoc[C];
  while(i!=D){
     i = Truoc[i];
     cout<<" <- "<<i+1;
  }
 }
// ham chinh
void main() {
   int A[max][max],n,Dau,Cuoi; // ma tan A chua do thi
   Doc_File(A,n,Dau,Cuoi);
   Dijkstra(A,n,Dau,Cuoi);
   getch();
}

/***** LƯU Ý ****/
- File Dijkstra.inp được đặt ở thư mục chứa code [Download file Dijkstra.inp tại đây], các bạn có thể tạo phải Dijkstra.inp khác tùy vào đồ thị mà bạn muốn kiểm tra
- Download code chương trình tại đây
- Khi download, bạn chờ 5s, click BỎ QUA QUẢNG CÁO (SKIN AD)

[Thuật toán đồ thị / code C++] Thuật toán Euler - tìm đường đi Euler trên đồ thị G (với đồ thị nửa Euler)

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất 1 lần.

Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách xóa cạnh đã đi qua trong quá trình tìm kiếm đường đi.

Mô tả dữ liệu đầu vào và đầu ra của bài toán:
+ Dữ liệu vào: cho trong tập tin Euler.inp
   - Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
   - Dòng i+1 (1 <= i <= n ) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
+ Dữ liệu ra: in ra màn hình đường đi qua tất cả các cạnh (nếu có).

[Cài đặt thuật toán với Turbo C++]

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Euler.inp"
int Dem = 0, SoCanh=0; //dem so duong di va luu so canh cua do thi
int *L; //luu dinh da di qua
int **A,n;
int XuatPhat=0; //dinh xuat phat la dinh bac le neu do thi co dinh bac le

// Doc file chua do thi G (dang ma tran ke)
void Doc_File() {
   int BacDinh; // Bac cua dinh
   FILE*f = fopen(Filename,"rb");
   fscanf(f,"%d",&n);
   cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<n<<endl;
   *A = new int [n];
   for(int i =0;i<n;i++) {
      A[i] = new int [n];
      BacDinh = 0;
      for(int j =0;j<n;j++) {
         fscanf(f,"%d",&A[i][j]);

         cout<<A[i][j]<<" ";
         if(A[i][j] == 1)
             BacDinh++;
}
  if(BacDinh%2==1)
   XuatPhat = i; //xuat phat tu dinh bac le (do thi nua Euler)
  SoCanh+=BacDinh;
  cout<<endl;
}
  fclose(f);
  SoCanh = SoCanh/2; //so canh = so dinh chia 2
  L = new int [SoCanh+1];
  L[0] = XuatPhat;
}

// In ra duong di Euler
void InDuongDi() {
  Dem++;
  cout<<endl<<XuatPhat+1;
  for (int i = 1; i<=SoCanh; i++)
    cout<<" -> "<<L[i]+1;
}

//thu tuc tim kiem de quy
void Try(int Canh) {
  if(Canh > SoCanh) //tim du so canh thi xuat duong di
     InDuongDi();
   else {
        for(int i = 0; i<n; i++)
           if( A[L[Canh-1]][i]>0){
              L[Canh] = i;
              A[L[Canh-1]][i]=A[i][L[Canh-1]]=0; //xoa canh
              Try(Canh+1); //tim canh tiep theo
              A[L[Canh-1]][i]=A[i][L[Canh-1]]=1; //phuc hoi canh
              L[Canh] = 0;
      }
  }
}

// ham chinh
void main() {
  Doc_File();
  cout<<"\n DUONG DI";
  Try(1);
   if(Dem==0)
      cout<<"\n KHONG CO";
   delete*A,L;
    getch();

}

/***** LƯU Ý ****/
- File Euler.inp được đặt ở thư mục chứa code [Download file Euler.inp tại đây], các bạn có thể tạo phải Euler.inp khác tùy vào đồ thị mà bạn muốn kiểm tra
- Download code chương trình tại đây
- Khi download, bạn chờ 5s, click BỎ QUA QUẢNG CÁO (SKIN AD)

[Algorithms] Cây quyết định với bài toán phân loại dữ liệu

Cây quyết định với bài toán phân loại dữ liệu

Khái niệm cây quyết định

Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút trong (internal node) tương ứng với một biến; đường nối giữa nó với nút con của nó thể hiện một giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho trước các giá trị của các biến được biểu diễn bởi đường đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định. [Xem thêm...]

[Algorithms] Thuật toán K-Mean trong bài toán Phân cụm dữ liệu [VB]

Thuật toán K-Mean trong bài toán Phân cụm dữ liệu


I. GIỚI THIỆU
Thuật toán K-means clustering do MacQueen giới thiệu trong tài liệu “J. Some Methods for Classification and Analysis of Multivariate Observations” năm 1967.
K-means Clustering là một thuật toán dùng trong các bài toán phân loại/nhóm n đối tượng thành k nhóm dựa trên đặc tính/thuộc tính của đối tượng (k £n nguyên, dương).
Về nguyên lý, có n đối tượng, mỗi đối tượng có m thuộc tính, ta phân chia được các đối tượng thành k nhóm dựa trên các thuộc tính của đối tượng bằng việc áp dụng thuật toán này.
Coi mỗi thuộc tính của đối tượng (đối tượng có m thuộc tính) như một toạ độ của không gian m chiều và biểu diễn đối tượng như một điểm của không gian m chiều. [Xem thêm...]

[ Java ] Lớp trừu tượng và phương thức trừu tượng (abstract) trong Java - Ví dụ 1: Tính điểm cho sinh viên [abstract class-method]

Lớp trừu tượng và phương thức trừu tượng (abstract) trong Java
Xây dựng Project theo mô hình sau:



Yêu cầu:
 - Khởi tạo mỗi lớp 1 đối tượng
 - In kết quả 

[Cài đặt với NetBean]
- Xây dựng Project như hình sau:



- Code Java:

/*abstract class SV*/
package abstract1;

public abstract class SV {
    // thuoc tinh
    int ns;// nam sinh
    String ht;// ho ten
    String dc;// dia chi
    // phuong thuc khoi tao
    public SV(String ht, int ns, String dc){
     this.ht=ht; this.dc=dc; this.ns=ns;   
    }    
    // Phuong thuc TinhDiem() - abstract
    abstract float TinhDiem();
    // phuong thuc XepLoai()-abstract
    abstract String XepLoai();
    // phuong thuc InKQ()
    void InKQ(){
        System.err.print("\n - Ho ten sinh vien: "+ht);
        System.err.print("\n - Dia chi: "+dc);
        System.err.print("\n - Nam sinh: "+ns);
        System.err.print("\n - Diem tong ket: "+TinhDiem());
        System.err.println("\n - Xep loai: "+XepLoai());
        
    }
}


/*class SVCD*/

public class SVCD extends SV{
    // thuoc tinh
    float dLT,dCSDL,dMang;
    // khoi tao
    public SVCD(String ht,int ns, String dc, float dLT,float dCSDL, float dMang){
        super(ht,ns,dc);
        this.dCSDL=dCSDL;
        this.dLT=dLT;
        this.dMang=dMang;
    }
    // Phuong thuc TinhDiem()
    float TinhDiem(){
        return (dCSDL+dLT+dMang)/3;
    }
    String XepLoai(){
        float d=TinhDiem();
        String xl="";
        if (d<5)
            xl="Khong dat";
        else if (d<6)
            xl="TB";
        else if(d<7)
            xl="TBK";
        else if(d<8)
            xl="Kha";
        else if(d<9)
            xl="Gioi";
        else xl="Xuat sac";
        return xl;
    }
}

/*class SVDH*/
package abstract1;
public class SVDH extends SVCD {
 // thuoc tinh
    float dCNPM;
    // khoi tao
    public SVDH(String ht,int ns, String dc, float dLT,float dCSDL, float dMang,float dCNPM){
        super(ht,ns,dc,dLT,dCSDL,dMang);        
        this.dCNPM=dCNPM;
    }
    // Phuong thuc TinhDiem()
    float TinhDiem(){
        return (dCSDL+dLT+dMang+dCNPM)/4;
    }
    String XepLoai(){
        float d=TinhDiem();
        String xl="";
        if (d<5)
            xl="Khong dat";
        else if (d<6)
            xl="TB";
        else if(d<7)
            xl="TBK";
        else if(d<8)
            xl="Kha";
        else if(d<9)
            xl="Gioi";
        else xl="Xuat sac";
        return xl;
    }
}

/*class Abstract1 (class chinh)*/
package abstract1;
public class Abstract1 {
    public static void main(String[] args) {
        // khai bao doi tuong SVCD
        SVCD t=new SVCD("Nguyen Van A",1990,"Ha Noi",7,8,9);
        t.InKQ();
        // khai bo doi tuong SVDH
        SVDH t1=new SVDH("Nguyen Van B",1989,"Ha Tay",6,7,8,9);
        t1.InKQ();
    }
}

>> Tài Project Tại đâyLưu ý: sau 5s, click BỎ QUA QUẢNG CÁO


Danh mục bài viết