Code PTTKGT
//Cài đặt giải thuật Insertion Sort
public static void insertion_sort(int A[])
{
int temp,j;
for (int i = 1; i <= A.length-1; i++)
{
temp = A[i];
// Insert A[i] into the sorted sequence A[0..i-1]
j = i - 1;
while (j >= 0 && A[j] > temp)
{
A[j+1] = A[j];
j = j - 1;
}
A[j+1] = temp;
}
}
//main function
public static void main(String[] args) {
int A[] = {5, 2, 10, 100, 25, 40, 250, 1000, 60, 500};
insertion_sort(A);
for(int i = 0; i<A.length; i++)
System.out.print(A[i]+" ");
}
//==============================^v^v^v^v^v^v===================================
//Cài đặt giải thuật Selection sort
public class SelectionSort {
// Sort by descending
public static void sort(int[] array) {
for (int i = 0; i < array.length; i++) {
int max = array[i]; // Lưu phần tử lớn nhất
int index = i; // lưu vị trí chứa phần tử lớn nhất
for (int j = i + 1; j < array.length; j++) {
if(max < array[j]){
max = array[j];
index = j;
}
}
// Nếu chỉ số đã thay đổi, ta sẽ hoán vị
if(index != i){
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
}
}
//==============================^v^v^v^v^v^v===================================
//Cài đặt giải thuật Buble sort
for(int i = 0; i< array.length; i++){
for (int j = array.length - 1; j > 0; j--) {
if(array[j] < array[j-1]){
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}
//==============================^v^v^v^v^v^v===================================
//Quick sort đệ quy
public int findPivot(int i, int j, int[] array) {
if (array.length == 1) {
return -1;
}
int k = i + 1;
int pivot = array[i];
while ((k <= j) && (array[k] == pivot)) {
k++;
}
if (k > j) {
return -1;
}
if (array[k] > pivot) {
return k;
} else {
return i;
}
}
// Tìm partition
public int pointPartition(int i, int j, int pivotKey, int[] array) {
int partition = -1;
int L = i;
int R = j;
while (L <= R) {
while (array[L] < pivotKey)
L++;
while (array[R] >= pivotKey)
R--;
if (L < R) {
int temp = array[L];
array[L] = array[R];
array[R] = temp;
}
}
partition = L;
return partition;
}
// Sắp xếp
public void quickSort(int i, int j, int[] array) {
int pivot = findPivot(i, j, array);
if (pivot == -1)
return;
int partition = pointPartition(i, j, array[pivot], array);
quickSort(i, partition - 1, array);
quickSort(partition, j, array);
}
// Test:
quickSort(0, array.length - 1, array);
//==============================^v^v^v^v^v^v===================================
//Quick sort không đệ quy
public static void Swap(int i, int j, int[] a)
{
int mid;
mid=a[i];
a[i]=a[j];
a[j]=mid;
}
public static void Quick(int a[],int Left,int Right)
{
int i,j,mid;
i=Left;
j=Right;
mid=a[(int)(Left+Right)/2];
do
{
while(a[i]<mid && i<Right)i++;
while(a[j]>mid && j>Left)j--;
if(i<=j)
{
Swap(i,j,a);
i++;
j--;
}
} while (i<=j);
if (Left<j)Quick(a,Left,j);
if(i<Right)Quick(a,i,Right);
}
public static void QuickSort(int a[],int n)
{
Quick(a,0,n-1);
}
//==============================^v^v^v^v^v^v===================================
//Cài đặt giải thuật Sequential Search
public static int sequential_search(int A[], int x)
{
int i = 0;
while (i <= A.length-1 && A[i] != x)
i = i + 1;
if (i == A.length) return -1;
return i;
}
//main function
public static void main(String[] args) {
int A[] = {5, 2, 10, 100, 25, 40, 250, 1000, 60, 500};
int k = 1000;
System.out.println(sequential_search(A,k));
}
//==============================^v^v^v^v^v^v===================================
//Cài đặt giải thuật tìm mẫu lặp lại nhiều lần nhất trong chuỗi thời gian
public static void find_motif (int T[], int n, int R)
{
int best_count = 0;
int best_loc = -1;
ArrayList index_list = new ArrayList();
for (int i=0; i<=T.length-n; i++)
{
int count = 0;
ArrayList temp = new ArrayList();
for (int j=0; j<=T.length-n; j++)
{
if (non_trival_match(T,i,j,n,R))
{
count++;
temp.add(j);
}
}
if (count > best_count)
{
best_count = count;
best_loc = i;
index_list = temp;
}
}
System.out.println(best_count+" "+best_loc);
for (int c = 0; c < index_list.size(); c++)
System.out.print(index_list.get(c)+" ");
}
public static boolean non_trival_match(int T[], int l, int u, int n, int R)
{
if (Math.abs(l-u) >= R)
{
int count = 0;
while (count < n)
{
if (T[l+count] != T[u+count])
return false;
count++;
}
return true;
}
else
return false;
}
public static void main(String[] args) {
int T[] = {1,2,3,0,1,2,3,7,8,1,2,3,4,1,2,3,1,2,3};
find_motif (T, 3, 2);
}
//==============================^v^v^v^v^v^v===================================
//Cài đặt giải thuật liệt kê các dãy nhị phân có độ dài n
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int x[] = new int[n];
for (i = 0; i < n; i++)
x[i] = 0;
do
{
for (i = 0; i < n; i++)
System.out.print(x[i]);
System.out.println();
i = n - 1;
while (i >= 0 && x[i] == 1)
i = i - 1;
if (i >= 0)
{
x[i] = 1;
for (int j = i+1; j < n; j++)
x[j] = 0;
}
}
while (i >= 0);
}
//==============================^v^v^v^v^v^v===================================
//Cho 2 chuỗi ký tự có độ dài khác nhau. Hãy tìm tất cả các vị trí xuất hiện của chuỗi ngắn trong chuỗi dài (nếu có).
import java.util.*;
public class bai6 {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String s1,s2,kq;kq="";
System.out.print("nhap chuoi 1:");;
s1=scanner.nextLine();
System.out.print("nhap chuoi 2:");;
s2=scanner.nextLine();
int i=0,length=s1.length()-s2.length()+1;
while(i<length)
{
int vitri=s1.indexOf(s2,i);
if(vitri<0)break;
i=vitri+1;
kq=kq+i+" ";
}
System.out.printf("vt chuoi '%s' trong chuoi '%s' la: %s",s2,s1,kq);
}
}
//==============================^v^v^v^v^v^v===================================
//Nhập vào danh sách n tên người. Liệt kê tất cả các cách chọn ra đúng k người trong số n người đó.
import java.util.*;
public class bai6 {
public static void lietketohop(String[] arrs, int k,int i,String s)
{
if(k==0)System.out.println(s);
else
{
int length= arrs.length;
if(k>length-i)return;
for(i=0;i<length;i++)
{
lietketohop(arrs,k-1,i+1,s+" "+arrs[i]);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.print("nhap so nguoi:");
//arrs[0]=scanner.nextLine();
Scanner scanner=new Scanner(System.in);
int n=Integer.parseInt(scanner.nextLine());
String[] arrs=new String[n];
arrs[0]=scanner.nextLine();
for(int i=0;i<n;i++)
{
System.out.printf("nguoi thu %d",i+1);
arrs[i]=scanner.nextLine();
}
System.out.print("nhap so nguoi can chon:");
int k=Integer.parseInt(scanner.nextLine());
lietketohop(arrs,k,0," ");
}
}
//==============================^v^v^v^v^v^v===================================
//Liệt kê tất cả các tập con của tập {1, 2, …, n}. Có thể dùng phương pháp liệt kê tập con hoặc dùng phương pháp liệt kê tất cả các dãy nhị phân. Mỗi số 1 trong dãy nhị phân tương ứng với một phần tử được chọn trong tập. Ví dụ với tập {1, 2, 3, 4} thì dãy nhị phân 1010 sẽ tương ứng với tập con {1, 3}. Hãy viết chương trình in ra tất cả các tập con của {1, 2, …, n} theo hai phương pháp.
import java.util.*;
public class bai6 {
/**
* @param args
*/
public static void lietketohop(String[] arrs, int k,int i,String s)
{
if(k==0)System.out.println(s);
else
{
int length= arrs.length;
if(k>length-i)return;
for(i=0;i<length;i++)
{
lietketohop(arrs,k-1,i+1,s+" "+arrs[i]);
}
}
}
public static void main(String[] args) {
System.out.print("nhap so phan tu cua tap hop:");
Scanner scanner=new Scanner(System.in);
int n=Integer.parseInt(scanner.nextLine());
String[] arrs=new String[n];
//arrs[0]=scanner.nextLine();
for(int i=0;i<n;i++)
{
System.out.printf("so thu %d",i+1);
arrs[i]=scanner.nextLine();
}
System.out.println("{"+"Null"+"}");
for(int j=1;j<=n;j++)
{
lietketohop(arrs,j,0," ");
}
}
}
//==============================^v^v^v^v^v^v===================================
//Cài đặt giải thuật tìm nhị phân
public class BinarySearch {
public static int bin_search (int A[], int key)
{
int left = 0;
int right = A.length-1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key == A[mid])
return mid;
else if (key < A[mid])
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
public static void main(String[] args) {
int A[] = {1, 2, 4, 8, 15, 50, 100};
System.out.println(bin_search(A,15));
}
}
//==============================^v^v^v^v^v^v===================================
//Cài đặt giải thuật Merge Sort
public class MergeSort {
public static void merge_sort (int A[], int p, int r)
{
if (p < r)
{
int q = (p + r) / 2;
merge_sort(A, p, q);
merge_sort(A, q+1, r);
merge(A, p, q, r);
}
}
private static void merge(int A[], int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int i, j, k;
int L[] = new int[n1+1];
int R[] = new int[n2+1];
for (i = 0; i < n1; i++)
L[i] = A[p+i];
for (j = 0; j < n2; j++)
R[j] = A[q+j+1];
L[n1] = Integer.MAX_VALUE;
R[n2] = Integer.MAX_VALUE;
i = 0;
j = 0;
for (k = p; k <= r; k++)
{
if (L[i] <= R[j])
{
A[k] = L[i];
i++;
}
else
{
A[k] = R[j];
j++;
}
}
}
public static void main(String[] args) {
int A[] = {3, 5, 1, 100, 20, 45, 75, 50, 8, 500, 1};
merge_sort(A,0,A.length-1);
for (int i = 0; i < A.length; i++)
System.out.print(A[i]+" ");
}
}
//==============================^v^v^v^v^v^v===================================
//Cho một tập hợp S có n số nguyên và số nguyên x. Tìm xem có tồn tại 2 phần tử nào trong S có tổng bằng x hay không.
import java.util.*;
public class hai {
/**
* @param args
*/
public static int giaithua(int n)
{
int k = 1;
for(int i = 1 ; i <= n ; i++)
{
k = k * i;
}
return k;
}
public static void main(String[] args)
{
// TODO Auto-generated method stub
int a[]={1 , 3 , 5 , 2 , 4 , 6 ,4 };
int t,x,kq=0,i=0,k=0,tang=1,dem=0;
System.out.print("Nhap vao x = ");
Scanner in = new Scanner(System.in);
x = in.nextInt();
t = (giaithua(a.length))/(2*giaithua(a.length-2));
System.out.println(t);
int b[] = new int[t];
int c[] = new int[t];
while(i < t)
{
kq = a[k] + a[k+tang];
if(kq == x)
{
b[dem] = a[k];
c[dem] = a[k+tang];
dem++;
}
i++;
tang++;
if(k+tang==a.length)
{
k++;
tang=1;
}
}
for(i = 0 ; i < dem ; i++)
{
System.out.print(b[i]+" ");
System.out.println(c[i]);
}
}
}
//==============================^v^v^v^v^v^v===================================
//Bài 5+6: Cài đặt giải thuật Depth-First-Search + Breadth-First-Search giải quyết bài toán duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó.
import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.util.Queue;
import java.util.Scanner;
public class bt {
public static void matran(Boolean[][] a)
{
for(int i=0;i<a.length;i++)
{
for(int j=0;j<a.length;j++)
{
if(i==j)
a[i][j]=true;
else
a[i][j]=false;
}
}
}
public static void xuat(Boolean[][] a)
{
for(int i=0;i<a.length;i++)
{
for(int j=0;j<a.length;j++)
{
System.out.print(a[i][j] + "\t");
}
System.out.println();
}
}
public static void nhapmatran(int i,int j,Boolean[][] a)
{
a[i][j]=true;
a[j][i]=true;
}
public static void DFS(int u,int n,Boolean[][] a,Boolean[] free)
{
for(int v=0;v<n;v++)
{
if(a[u][v]==true && free[v]==false)
{
System.out.print(v + "\t");
free[v]=true;
DFS(v,n,a,free);
}
}
}
public static void brFS(int s,int n,Boolean[][] a,Boolean[] free)
{
int front=0,rear=0;
int chua[]=new int[n];
chua[0]=s;
do{
int u=chua[front];
front++;
for(int v=0;v<n;v++)
{
if(a[u][v]==true && free[v]==false)
{
System.out.print(v + "\t");
free[v]=true;
rear++;
chua[rear]=v;
}
}
}while(rear>=front);
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
Boolean[][] A=new Boolean[n][n];
matran(A);
xuat(A);
int i,j;
do
{
System.out.println("nhap diem dau:");
i=in.nextInt();
System.out.println("nhap diem sau: ");
j=in.nextInt();
nhapmatran(i, j, A);
}
while(i!=0 || j!=0);
xuat(A);
Boolean free[]=new Boolean[n];
for(int z=0;z<n;z++)
free[z]=false;
//DFS(0,n,A,free);
brFS(0,n,A,free);
}
}
//==============================^v^v^v^v^v^v===================================
//Tính thời gian thực thi giải thuật
public static void main(String[] args) {
int A[] = {1, 5, 2, 10, 100, 25, 40, 300, 250, 1000, 60, 500, 1000, 1};
long startTime = System.nanoTime();
for (int count = 0; count < 100; count++)
insertion_sort(A);
long endTime = System.nanoTime();
System.out.println(endTime - startTime);
}
Bạn đang đọc truyện trên: Truyen247.Pro