Thứ Tư, 30 tháng 11, 2016

Cài đặt thuật toán Dijskstra bằng java

Bố cuc:
1. Lớp Bài toán: Cài đặt thuật toán Dijstra
2.Lớp test

1 .Lớp cài đặt thuật toán Dijkstra
BaiToan.java
package baocaovantruhoc_nhom13;

/**
 *
 * @TranVanLinh
 */
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;

public class BaiToan
{
    int soDinh;//so dinh cua do thi
    int G[][];//ma tran trong so
    int diemDau;//diem dau
    int doDai[];//do dai toi dinh i
    int daXet[];// danh dau la dinh co duong di la ngan nhat
    int dinhTruoc[];//luu vet dinh truoc
    int oo = 0;//gia tri vo cung
    public BaiToan()
    {
        soDinh = 0;
        G = null;
        doDai = null;
        daXet=null;
        dinhTruoc = null;
        diemDau = 0;
        oo = 0;
    }
    //Doc du lieu
    public boolean getDuLieuTuFile(String tenfile)
    {
        String chuoifile[]=tenfile.split(".");
        String path="G://"+tenfile;
        try
        {
            File file=new File(path);
            if(!file.exists())
            {
                return false;
            }
            FileInputStream input = new FileInputStream(path);
            InputStreamReader istream=new InputStreamReader(input);
            BufferedReader reader=new BufferedReader(istream);
            String sc;
            //doc so dinh cua do thi , dinh bat dau , dinh dich
            sc = reader.readLine();
            String temp[] = sc.split(" ");
            soDinh = Integer.parseInt(temp[0]);
            diemDau = Integer.parseInt(temp[1]);
            G=new int[soDinh][soDinh];
            int row=0;
            //doc matran do thi
            while ((sc = reader.readLine()) != null)
            {
                temp = sc.split(" ");
                for (int col = 0; col < soDinh; col++)
                {
                     G[row][col] = Integer.parseInt(temp[col]);
                }
                row++;
            }
          
            //dong file
            reader.close();
            istream.close();
            input.close();
        }
        catch(FileNotFoundException ex)
        {
            System.err.println("LOi file");
        }
        catch (IOException ex)
        {
                System.err.println("Ngoai le xay ra.!");
        }
        return true;
    }
    public void thuatToan_Dijkstra()
    {
        oo=999999999;
        //Gan trong so cho cac canh khong co duong di la vong cung
        for (int i = 0; i < soDinh; i++)
        {
            for (int j = 0; j < soDinh; j++)
            {
                if (i != j && G[i][j] == 0)
                {
                    G[i][j] = oo;
                }
            }
        }
        diemDau--;
        doDai= new int[soDinh];
        daXet=new int[soDinh];
        dinhTruoc=new int[soDinh];
        for (int i = 0; i < soDinh; i++)
        {
            doDai[i] = oo;                   // khoi tao do dai tu a toi moi dinh la vo cung
            daXet[i] = 0;                       // danh sach cac diem da xet
            dinhTruoc[i] = diemDau;                   // dat diem bat dau cua moi diem la a
        }
        int i=0;
         //Khoi tao d(diemDau,diemDau)=0;
        doDai[diemDau] = 0;
        for(int dinh=0;dinh<soDinh;dinh++)
        {
               for (i = 0; i < soDinh; i++)   // tim mot diem chua xet ma co duong di < vo cung
               {
                   if (daXet[i] != 1 && doDai[i] < oo)
                   {
                       break;
                   }
               }
               if(i==soDinh)//khong co dinh nao thoa man
               {
                   break;
               }
               for (int j = 0; j < soDinh; j++)// tim dinh ma co do dai la nho nhat
               {  
                   if (daXet[j]!=1 && doDai[i] > doDai[j])
                   {
                       i = j;
                   }
               }
               daXet[i] = 1;    // cho i vao danh sach xet roi
         
               for (int j = 0; j < soDinh; j++) // tinh lai do dai cua cac diem chua xet
               {  
                   if (daXet[j]!=1 && doDai[i] + G[i][j] < doDai[j])
                   {
                       doDai[j] = doDai[i] + G[i][j];   // thay doi do dai cua d[i,j]
                       dinhTruoc[j] = i;                       // danh dau diem truoc j la i
                   }
               }
        }
    }
    public  void inDuongDi()
    {
        for(int dinh=0;dinh<soDinh;dinh++)
        if(dinh!=diemDau)
        {
             //in duong di
            if(doDai[dinh] < oo)
            {
                System.out.print("\t\tĐộ dài đường đi từ đỉnh " + ((char)(diemDau+65)) + " đến đỉnh " +  ((char)(dinh+65)) + " là: " + doDai[dinh]+"\t----");
                int mang[] = new int[soDinh];
                int dem = 0;
                int i=dinh;
                while (i != diemDau)
                {
                    mang[dem++] = i;
                    i = dinhTruoc[i];
                }
                System.out.print("\tChi tiết: " +  ((char)(diemDau+65)));
                for (int k = dem - 1; k >= 0; k--) {
                    System.out.print("-->" + (char)(mang[k]+65));
                }
            }
            else
            {
                System.out.println("\t\tKhông có đường đi từ đỉnh "+( ((char)(diemDau+65)))+" đến đỉnh " + ( ((char)(dinh+65))));
            }
            System.out.println("\n");
        }
    }
    public  void inDuong2Di()
    {
        System.out.println("Nhap dinh dich: ");
        Scanner sc=new Scanner(System.in);
        int diemCuoi=sc.nextInt();
      
     
             //in duong di
            if(doDai[diemCuoi] < oo)
            {
                System.out.print("\t\tĐộ dài đường đi từ đỉnh " + ((char)(diemDau+65)) + " đến đỉnh " +  ((char)(diemCuoi+65)) + " là: " + doDai[diemCuoi]+"\t----");
                int mang[] = new int[soDinh];
                int dem = 0;
                int i=diemCuoi;
                while (i != diemDau)
                {
                    mang[dem++] = i;
                    i = dinhTruoc[i];
                }
                System.out.print("\tChi tiết: " +  ((char)(diemDau+65)));
                for (int k = dem - 1; k >= 0; k--) {
                    System.out.print("-->" + (char)(mang[k]+65));
                }
            }
            else
            {
                System.out.println("\t\tKhông có đường đi từ đỉnh "+( ((char)(diemDau+65)))+" đến đỉnh " + ( ((char)(diemCuoi+65))));
            }
            System.out.println("\n");
      
    }
    public void inMatran()
    {
        for(int i=0;i<soDinh;i++)
        {
            System.out.print("\t\t");
            for(int j=0;j<soDinh;j++)
            {
                if(G[i][j]==0)
                {
                    System.out.print("oo\t");
                }
                else
                {
                    System.out.print(G[i][j]+"\t");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

2. Lớp test 
BaoCaoVanTruHoc_Nhom13.java
 package baocaovantruhoc_nhom13;
import java.util.Scanner;

/**
 *
 * @TranVanLinh
 *
 */
public class BaoCaoVanTruHoc_Nhom13 {

    public static void main(String[] args)
    {
        System.out.println("\t\t\tBáo Cáo Bài Tập Lớn Môn Vận Trù Học");
        System.out.println("\t\tNhóm 13\tĐề tài: Cài đặt thuật toán Dijkstra\n");
       
        String tenTapTin;
        BaiToan thuatToan;
        do
        {
            System.out.print("\t\tNhập tên tập tin (.txt) : ");
            tenTapTin=(new Scanner(System.in)).nextLine();
            System.out.println("");
            thuatToan=new BaiToan();
            if(!thuatToan.getDuLieuTuFile(tenTapTin))
            {
                System.out.println("\t\tTập tin không tồn tại, Nhập lại.!");
            }
        }while(!thuatToan.getDuLieuTuFile(tenTapTin));
        System.out.println("\t\tMa trận kề : ");
        thuatToan.inMatran();
        thuatToan.thuatToan_Dijkstra();
        thuatToan.inDuongDi();
    }
}

Vd: Tìm đường đi của từ đỉnh x1 đến tất cả các đỉnh của đồ thị sau:



File input2.txt

 7 4
0 3 5 4 2 7 5
3 0 0 0 2 0 0
5 0 0 4 0 3 0
4 0 4 0 0 0 2
2 2 0 0 0 0 4
7 0 3 0 0 0 6
5 0 0 2 4 6 0


Kết quả:



Thứ Sáu, 11 tháng 11, 2016

Lập trình hướng đối tượng với Java số 11

1. Lớp HinhCN

public class HinhCN implements Comparable
{
    private double cdai;
    private double crong;
   
    public HinhCN()
    {
    }
    public HinhCN(double cdai,double crong)
    {
        this.cdai=cdai;
        this.crong=crong;
    }
   
    public double getCRong()
    {
        return crong;
    }
     public double getCDai()
    {
        return cdai;
    }
  public void setCRong(double a)
    {
          this.crong=a;
    }
     public void setCDai(double a))
    {
         this.cdai=a;

    }
    public double tinhDT()
    {
        return cdai*crong;
    }
    public double tinhCV()
    {
        return (cdai+crong)*2;
    }

    public boolean equals(HinhCN h2)
    {
        if(this.tinhDT()==h2.tinhDT())
        {
            return true;
        }
        return false;
    }
   
    public int compareTo(Object h2)
    {
        HinhCN hcn=(HinhCN)h2;
        if(this.tinhDT()<hcn.tinhDT())
        {
            return -1;
        }
        if(this.tinhDT()==hcn.tinhDT())
        {
            return 0;
        }
        return 1;
    }
}

2.Lớp test

public class Test
{
    public static void main(String [] args)
    {
        HinhCN a=new HinhCN(5,6);
        HinhCN b=new HinhCN(5,6);
        System.out.println("Su dung phuong thuc equals: ");
        if(a.equals(b))
        {
            System.out.println("Dien tich hai hinh bang nhau");
        }
        else
        {
            System.out.println("Dien tich hai hinh khong bang nhau");
        }
       
        HinhCN c=new HinhCN(9,9);
        HinhCN d=new HinhCN(10,9);
        System.out.println("Su dung phuong thuc compareTo: ");
        if(c.compareTo(d)==-1)
        {
            System.out.println("Dien tich c<d");
        }
        else if(c.compareTo(d)==0)
        {
            System.out.println("Dien tich c=d");
        }else
        {
             System.out.println("Dien tich c>d");
        }
    }
}

3.Kết quả:



Chủ Nhật, 30 tháng 10, 2016

Quản Lý Sinh Viên Với Node.js

Cấu trúc gồm có các hàm :
          Hàm : getAllSV();
Hàm : addSV();
Hàm: getSV();
Hàm : hienAllSV();
Hàm: editSV();
Hàm : xoaSV();
Hàm : hienSV();

var storage = require('node-persist');

var student={id:"",name:""};
storage.initSync();

//get toan bo sv
function getAllSV()
{
          var student=storage.getItemSync('student');
          if(typeof student == "undefined")
          {
                   return [];
          }
          return student;
}

// them sv
function addSV(id,name)
{
          var sv=getAllSV();
          for(var i=0;i<sv.length;i++)
          {
                   if(sv[i].id==id)
                   {
                             console.log("Id nay da ton tai");
                             return;
                   }
          }
          sv.push({
                   id:id,
                   name:name
          });
          storage.setItemSync("student",sv);
}

//get thong sv theo id
function getSV(id)
{
          var sv=getAllSV();
          for(var i=0;i<sv.length;i++)
          {
                   if(sv[i].id==id)
                             return sv[i];
          }
}

//hien tat ca cac sv
function hienAllSV()
{
          var sv=getAllSV();
          for(var i=0;i<sv.length;i++)
          {
                   console.log(sv[i].id+ "   "+sv[i].name);
          }
}

//sua sv
function editSV(id,name)
{
          var sv=getAllSV();
          for(var  i=0;i<sv.length;i++)
          {
                   if(sv[i].id==id)
                   {
                             sv[i].name=name;
                   }
          }
          storage.setItemSync("student",sv);
}
//xoa sv theo id
function xoaSV(id)
{
          var sv=getAllSV();
          for(var i=0;i<sv.length;i++)
          {
                   if(sv[i].id==id)
                   {
                             sv.splice(i,1);
                   }
          }
          storage.setItemSync("student",sv);
}

//hien thong tin mot sv
function hienSV(sv)
{
          console.log(sv.id+ "---"+sv.name);
}
addSV(1,"Tran van Linh");
addSV(2,"Bui van A");
addSV(3,"Le tat tung");
addSV(4,"Bui Hai Nam");
addSV(5,"Tran trong nghia");

var sv=getSV(1);
console.log("Tat ca SV: ");
hienAllSV();

xoaSV(1);
console.log("Sau khi xoa sv co id=1:");

hienAllSV();

var sv=getSV(2);
console.log("Thong tin sv co id=2:");
hienSV(sv);

console.log("Thong tin sv co khi edit sv co id=2:");
editSV(2,"La Hai Nam")
var edit=getSV(2);
hienSV(edit);
   
   Kết quả khi run: