সার্চিং এ্যালগরিদম (Searching algorithm)


সার্চিং প্রোগ্রামিং এর ক্ষেত্রে একটি অত্যন্ত গুরুত্বপূর্ণ বিষয়। সিংহভাগ প্রোগ্রামের ক্ষেত্রেই কোন না কোন সার্চ আমাদের করতে হয়। সার্চিংয়ের ক্ষেত্রে লিনিয়ার সার্চ, বাইনারী সার্চ, ব্রেথ ফার্স্ট সার্চ(BFS), ডেপথ ফার্স্ট সার্চ(DFS) ইত্যাদি জনপ্রিয় এ্যালগরিদম। তবে BFS এবং DFS গ্রাফের সাথে সম্পর্কিত বলে আজকে এ বিষয়ে আলোচনা করব না।
লিনিয়ার সার্চঃ
লিনিয়ার সার্চ হল সবচেয়ে সহজ এবং সর্বাধিক ব্যবহৃত সার্চিং এ্যালগরিদম। এই এ্যালগরিদমের ক্ষেত্রে একসারি তথ্যের(ডাটা) মধ্য থেকে কাঙ্খিত তথ্যটি খুজে পাওয়ার জন্য একটি একটি করে সবগুলো ডাটা খুঁজে দেখা। যদি কাঙ্খিত ডাটাটি খুঁজে পাওয়া যায় তবে খোঁজা বন্ধ করে দেয়া হয়।
সুবিধাঃ

  • কোড করা অনেক সহজ।
  • ডাটা যে অবস্থাতেই থাক না কেন খুঁজে পাওয়া সম্ভব।
  • অল্প সংখ্যক ডাটা থেকে কাঙ্খিত ডাটা খোঁজার জন্য অত্যন্ত উপযোগী।

অসুবিধাঃ

  • তথ্য খুঁজে পেতে অনেক বেশি সময় লাগে।
  • অধিক পরিমানে তথ্যের মধ্য থেকে খোঁজার জন্য উপযোগী নয়।

C++ প্রোগ্রামিং ভাষায় সোর্স কোডঃ

//Linear search

#include<iostream>
using namespace std;

int linear_search(int *a,int size, int key){
    for(int i=0;i<size;i++)
        if(a[i] == key)
            return i+1;
    return 0;
    }

int main(){
    int n, key;
    cout<<"How many number do you want: ";
    cin>>n;
    int arr[n];
    cout<<"Enter "<<n<<" numbers:"<<endl;
    for(int i=0;i<n;i++)
        cin>>arr[i];
    cout<<"Enter the searching number: ";
    cin>>key;
    int res = linear_search(arr, n, key);
    if(res==0)
        cout<<"Key not found."<<endl;
    else
        cout<<"Key found at position "<<res<<"."<<endl;
    return 0;
    }

Java প্রোগ্রামিং ভাষায় সোর্স কোডঃ

//Linear Search

import java.util.Scanner;

public class LinearSearch{
    public static int linearSearch(int a[], int key){
        for(int i=0;i<a.length;i++)
            if(a[i] == key)
                return i+1;
        return 0;
        }

    public static void main(String args[]){
        Scanner input = new Scanner(System.in);
        System.out.println("Linear Search");
        System.out.print("Enter the number of element in array: ");
        int n = input.nextInt();
        int arr[] = new int[n];
        System.out.print("Enter " + n + " numbers: ");
        for(int i=0;i<n;i++)
            arr[i] = input.nextInt();
        System.out.print("Enter the searching key: ");
        int key = input.nextInt();
        if(linearSearch(arr, key) != 0)
            System.out.println("Key found at " + linearSearch(arr, key) + " position.");
        else
            System.out.println("Key not found.");
        }
    }

বাইনারী সার্চঃ
বাইনারী সার্চ সবচেয়ে কার্যকর সার্চিং এ্যালগরিদম। এর মাধ্যমে খুব কম সময়ে বিপুল পরিমান তথ্যের মধ্য থেকে কাঙ্খিত তথ্যটি খুঁজে পাওয়া যায়। এর জন্য ডাটাগুলোকে সর্টিং বা সাজানো অবস্থায় থাকা লাগে। সাজানো ডাটা গুলোর মধ্য থেকে মাঝের ডাটাটিকে নিয়ে প্রথমে চেক করা হয়। যদি আমার কাঙ্খিত ডাটা মাঝের ডাটা থেকে বড় হয় তবে মাঝের ডাটাটির চেয়ে ছোট সবগুলোকে বাদ দিয়ে আবার মাঝের ডাটা বের করা হয়। এভাবে কাঙ্খিত তথ্য খুঁজে না পাওয়া পর্যন্ত এ প্রক্রিয়া চালানো হয়।
সুবিধাঃ

  • খুব অল্প সময়ের মধ্যে তথ্য খুঁজে বের করা যায়।
  • বিপুল পরিমান তথ্য খোঁজার জন্য খুবই উপযোগী।

অসুবিধাঃ

  • তথ্য সর্টেড বা সাজানো থাকতে হয়।
  • অল্প পরিমান ডাটা খোঁজার জন্য খুব বেশি ফলপ্রসূ হয় না।

C++ প্রোগ্রামিং ভাষায় সোর্স কোডঃ

//Binary search

#include<iostream>
#include<algorithm>
using namespace std;

int binary_search(int a[], int size, int key){
        int beg = 0, end = size-1;
        int mid = (beg+end)/2;
        while(beg<=end){
            if(key<a[mid])
                end = mid-1;
            else
                beg = mid+1;
            if(a[mid]==key)
                break;
            mid = (beg+end)/2;
            }
        if(a[mid]==key)
            return mid+1;
        return 0;
        }

int main(){
    int n, key;
    cout<<"How many number do you want: ";
    cin>>n;
    int arr[n];
    cout<<"Enter "<<n<<" numbers:"<<endl;
    for(int i=0;i<n;i++)
        cin>>arr[i];
    sort(arr, arr+n);
    cout<<"Sorted elements are:"<<endl;
    for(int i=0;i<n;i++)
        cout<<arr[i]<<" ";

    cout<<"Enter the searching number: ";
    cin>>key;
    int res = binary_search(arr, n, key);
    if(res==0)
        cout<<"Key not found."<<endl;
    else
        cout<<"Key found at position "<<res<<"."<<endl;
    return 0;
    }

Java প্রোগ্রামিং ভাষায় সোর্স কোডঃ

//Binary Search

import java.util.Scanner;

public class BinarySearch{
    public static int binarySearch(int a[], int key){
        int beg = 0, end = a.length-1;
        int mid = (beg+end)/2;
        while(beg<=end){
            if(key<a[mid])
                end = mid-1;
            else
                beg = mid+1;
            if(a[mid]==key)
                break;
            mid = (beg+end)/2;
            }
        if(a[mid]==key)
            return mid+1;
        return 0;
        }

    public static void bubbleSort(int a[]){
        for(int i=0; i<a.length-1; i++){
            for(int j=i+1; j<a.length; j++){
                if(a[i]>a[j]){
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    }
                }
            }
        }

    public static void main(String args[]){
        Scanner input = new Scanner(System.in);
        System.out.println("Binary Search");
        System.out.print("Enter the number of element in array: ");
        int n = input.nextInt();
        int arr[] = new int[n];
        System.out.print("Enter " + n + " numbers: ");
        for(int i=0;i<n;i++)
            arr[i] = input.nextInt();
        bubbleSort(arr);
        System.out.print("Array after sorting: ");
        for(int i: arr)
            System.out.print(i + " ");
        System.out.println();
        System.out.print("Enter the searching key: ");
        int key = input.nextInt();
        if(binarySearch(arr, key)!=0)
            System.out.println("Key found at "+ binarySearch(arr, key) + " potision.");
        else
            System.out.println("Key not found.");
        }
    }

ডাটা স্ট্রাকচারঃ Two Way Linked List


জাভাতে C বা C++ এর মত পয়েন্টার নাই। পয়েন্টারের কাজ জাভাতে reference এর মাধ্যমে করা হয়। সাধারন বা ওয়ান ওয়ে লিঙ্ক লিস্টের মত খুব সহজেই জাভা প্রোগ্রামিং ভাষা ব্যবহার করে টু ওয়ে লিঙ্ক লিস্ট তৈরী করা যায়।

কোডঃ

//Two Way Linked List
//Author: Milon

import java.util.NoSuchElementException;

//Node class
class Node{
	//Instance variable
	private Object data;
	private Node nextNode;
	private Node previousNode;

	//Constructor
	public Node(){
		data = null;
		nextNode = null;
		previousNode = null;
		}

	public Node(Object item, Node next, Node previous){
		data = item;
		nextNode = next;
		previousNode = previous;
		}

	//Set methods
	public void setData(Object item){
		data = item;
		}

	public void setNextNode(Node next){
		nextNode = next;
		}

	public void setPreviousNode(Node previous){
		previousNode = previous;
		}

	//Get methods
	public Object getData(){
		return data;
		}

	public Node getNextNode(){
		return nextNode;
		}

	public Node getPreviousNode(){
		return previousNode;
		}

	//Overloaded toString() method
	public String toString(){
		return ("" + data);
		}
	}


//Two Way Linked List class

public class TwoWayLinkedList{
	//Instance variable
	private int size;
	private Node head;
	private Node tail;

	//Constructor
	public TwoWayLinkedList(){
		head = tail = null;
		size = 0;
		}

	//Returns is the list empty
	public boolean isEmpty(){
		return head == null;
		}

	//Returns the size of list
	public int size(){
		return size;
		}

	//Insert element at first position
	public void addFirst(Object item){
		if(isEmpty()){
			head = tail = new Node(item, head, tail);
			++size;
			return;
			}
		Node current = new Node(item, head, null);
		head.setPreviousNode(current);
		head = current;
		++size;
		}

	//Insert an element at last
	public void addLast(Object item){
		if(isEmpty()){
			addFirst(item);
			return;
			}
		Node current = new Node(item, null, tail);
		tail.setNextNode(current);
		tail = current;
		++size;
		}

	//Show the first item
	public Object showFirst(){
		if(!isEmpty())
			return head.getData();
		else{
			System.out.println("LinkedList is empty.");
			//throw new NoSuchElementException();
			return null;
			}
		}

	//Show the last item
	public Object showLast(){
		if(!isEmpty())
			return tail.getData();
		else{
			System.out.println("LinkedList is empty.");
			//throw new NoSuchElementException();
			return null;
			}
		}

	//Remove the first element
	public Object removeFirst(){
		if(head.getNextNode() == null){
			Node current = head;
			head = null;
			tail = null;
			--size;
			return current.getData();
			}
		if(!isEmpty()){
			Node current = head;
			head = head.getNextNode();
			head.setPreviousNode(null);
			--size;
			return current.getData();
			}
		else{
			System.out.println("LinkedList is empty.");
			//throw new NoSuchElementException();
			return null;
			}
		}

	//Remove the last element
	public Object removeLast(){
		if(isEmpty()){
			System.out.println("LinkedList is empty.");
			//throw new NoSuchElementException();
			return null;
			}
		if(head.getNextNode() == null){
			--size;
			return removeFirst();
			}
		Node current = tail;
		tail = tail.getPreviousNode();
		tail.setNextNode(null);
		--size;
		return current.getData();
		}

	//Check does the item exists in the list
	public boolean contains(Object item){
		Node current = head;
		while(current.getNextNode() != null){
			if(item.equals(current.getData()))
				return true;
			else
				current = current.getNextNode();
			}
		return false;
		}

	//Traversing the list from front
	public String frontTraverse(){
		String str = "[ ";
		if(head != null){
			str += head.getData();
			Node current = head.getNextNode();
			while(current.getNextNode() != null){
				str += ", " + current.getData();
				current = current.getNextNode();
				}
			str += ", " + current.getData();
			}
		str += " ]";
		return str;
		}

	//Traversing the list from rear
	public String rearTraverse(){
		String str = "[ ";
		if(tail != null){
			str += tail.getData();
			Node current = tail.getPreviousNode();
			while(current.getPreviousNode() != null){
				str += ", " + current.getData();
				current = current.getPreviousNode();
				}
			str += ", " + current.getData();
			}
		str += " ]";
		return str;
		}

	}
//Two Way Linked List Implementation class
//Author: Milon

import java.util.Scanner;
import java.util.Random;

public class TwoWayLinkedListImplement{
	public static void main(String args[]){
		TwoWayLinkedList list = new TwoWayLinkedList();
		Scanner input = new Scanner(System.in);
		Random rand = new Random();

		System.out.print("How many item do you want to insert first: ");
		int n = input.nextInt();

		for(int i=0;i<n;i++)
			list.addFirst(new Integer(rand.nextInt(100)));

		while(true){
			System.out.println("\n");
			System.out.println("* * * * * TwoWayLinkedList Implementation * * * * *");
			System.out.println(" 1. Show the list from front.");
			System.out.println(" 2. Show the list from rear.");
			System.out.println(" 3. Insert an element at first position.");
			System.out.println(" 4. Insert an element at last position.");
			System.out.println(" 5. Show the first element.");
			System.out.println(" 6. Show the last element.");
			System.out.println(" 7. Show the list size.");
			System.out.println(" 8. Search an element in the list.");
			System.out.println(" 9. Remove first element.");
			System.out.println("10. Remove last element.");
			System.out.println("11. Exit\n\n");

			System.out.print("Enter your choice: ");
			int choice = input.nextInt();

			switch(choice){
				case 1:
						System.out.println("The whole list from front is:");
						System.out.println(list.frontTraverse());
						break;

				case 2:
						System.out.println("The whole list from rear is:");
						System.out.println(list.rearTraverse());
						break;

				case 3:
						System.out.print("Enter the element: ");
						int item = input.nextInt();
						list.addFirst(new Integer(item));
						System.out.println("Item inserted successfully.");
						break;

				case 4:
						System.out.print("Enter the element: ");
						int element = input.nextInt();
						list.addLast(new Integer(element));
						System.out.println("Item inserted successfully.");
						break;

				case 5:
						System.out.println("The first element is: "+list.showFirst());
						break;

				case 6:
						System.out.println("The last element is: "+list.showLast());
						break;

				case 7:
						System.out.println("List size is: "+list.size());
						break;

				case 8:
						System.out.print("Enter the searching element: ");
						int key = input.nextInt();
						if(list.contains(key))
							System.out.println("Item found.");
						else
							System.out.println("Item not found.");
						break;

				case 9:
						System.out.println("First element " + list.removeFirst() + " removed.");
						break;

				case 10:
						System.out.println("Last element " + list.removeLast() + " removed.");
						break;

				case 11:
						System.exit(1);
						break;

				default:
						break;
				}
			}
		}

	}

মৌলিক সংখ্যা (Prime number)


Prime number বা মৌলিক সংখ্যা হচ্ছে সে সব সংখ্যা যার ১ এবং ঐ সংখ্যা ছাড়া আর কোন উৎপাদক নেই। অর্থাৎ ঐ সংখ্যাটি ১ এবং ঐ সংখ্যা ছাড়া নিঃশেষে বিভাজ্য নয়।

প্রোগ্রামারদের কাছে মৌলিক সংখ্যা খুব পছন্দের একটা বিষয়। যে কোন ধরনেন প্রোগ্রামিং প্রতিযোগিতায় সাধারনত অন্তত একটা সমস্যা থাকে প্রাইম নাম্বার থেকে। প্রাইম নাম্বার বের করার প্রোগ্রামটি খুব সহজেই লিখে ফেলা যায়।

কোডঃ

//Prime number check
//Author: Milon

#include<iostream>
using namespace std;

bool isPrime(int num){
    if(num<2)
        return false;
    for(int i=2;i<num;i++)
        if(num%i==0)
            return false;
    return tru e;
    }

int main(){
    int n;
    while(cin>>n && n){
        if(isPrime(n))
            cout<<n<<" is a prime number."<<endl;
        else
            cout<<n<<" is not a prime number."<<endl;
        }
    return 0;
    }

উপরের প্রোগ্রামটিতে সব গুলো সংখ্যা দিয়ে num কে ভাগ করা হয়েছে, যার আসলে কোন প্রয়োজন নেই। কারন কোন জোড় সংখ্যা কখনো প্রাইম নাম্বার হতে পারে না।
সেক্ষেত্রে প্রোগ্রামটি হবে-

কোডঃ

//Prime number check
//Author: Milon

bool isPrime(int num){
    if(num<2)
        return false;
    if(num==2)
        return true;
    if(num%2==0)
        return false;
    for(int i=3;i<num;i+=2)
        if(num%i==0)
            return false;
    return true;
    }

এখানেও শেষ পর্যন্ত চেক করা হয়েছে। যার আসলে দরকার নেই। কারন ঐ সংখ্যাটি মৌলিক কিনা তা চেক করার জন্য ঐ সংখ্যার অর্ধেক পর্যন্ত চেক করলেই চলে। সেক্ষেত্রে প্রোগ্রামটি হবে-

কোডঃ

//Prime number check
//Author: Milon

bool isPrime(int num){
    if(num<2)
        return false;
    if(num==2)
        return true;
    if(num%2==0)
        return false;
    for(int i=3;i<num/2;i+=2)
        if(num%i==0)
            return false;
    return true;
    }

অর্ধেক পর্যন্ত চেক করার প্রয়োজনও আসলে নাই। ঐ সংখ্যার বর্গমূল পর্যন্ত চেক করলেই চলে-

কোডঃ

//Prime number check
//Author: Milon

bool isPrime(int num){
    if(num==1)
        return false;
    if(num==2)
        return true;
    if(num%2==0)
        return false;
    for(int i=3;i*i<=num;i+=2)
        if(num%i==0)
            return false;
    return true;
    }

প্রাইম নাম্বার বের করার সবচেয়ে ভাল পদ্ধতি হচ্ছে Sieve of Eratosthenes. গ্রীক গণিতবিদ Eratosthenes এই পদ্ধতিটি আবিস্কার করেন। এই পদ্ধতিটিতে প্রথমে যে সংখ্যাগুলোর মধ্য থেকে প্রাইম নাম্বার বের করা হবে সেগুলিকে একটা অ্যারের মধ্যে রাখা হয়। মনে করি আমরা ১ থেকে ৫০ পর্যন্ত সংখ্যার মধ্যে প্রাইম নাম্বার বের করব। তাহলে prime নামের অ্যারের মধ্যে আমরা সংখ্যাগুলোকে রাখব। আমরা ধরে নিলাম এর সবগুলোই প্রাইম নাম্বার।
প্রথমে ০ এবং ১ প্রাইম নাম্বার না। তাই এ দুটোকে বাদ দিলাম। ২ প্রাইম সংখ্যা, কিন্তু এর গুনিতক একটাও প্রাইম নাম্বার না। তাই ৪, ৬, ৮, ১০, ১২ এগুলোকে বাদ দিলাম। এরপরের প্রাইম নাম্বার ৩। ৩ এর সব গুনিতক বাদ। এরপর ৪, কিন্তু ৪ আগেই বাদ পড়েছে। এরপর ৫ প্রাইম নাম্বার, ৫ এর সব গুনিতক বাদ। এভাবে চলতে চলতে ৫০ এর বর্গমূল পর্যন্ত চেক করলেই আমরা সব প্রাইম নাম্বার পেয়ে যাব।

কোডঃ

//Sieve of Eratosthenes
//Author: Milon

#include<cstdio>
#include<cmath>
using namespace std;

#define max 19000000

bool prime[max+1];

void sieve(){
    long int i,j;
    for(i=2;i<=max;i++)
        prime[i]=true;
    for(i=2;i*i<=max;){
        for(j=2*i;j<=max;j+=i){
            prime[j]=false;
            }
        i++;
        while(!prime[i])
            i++;
        }
    }

int main(){
    sieve();
    long int n;
    while(scanf("%ld",&n)==1){
        if(prime[n]==true)
            printf("prime\n");
        else
            printf("not prime\n");
        }
    return 0;
    }

ডাটা স্ট্রাকচারঃ Weighted Graph


যে গ্রাফের প্রত্যেকটা এজের(edge) একটা Weight বা মান দেয়া থাকে তাকে Weighted Graph বলে। Weighted graph তৈরীর কৌশল হল-

কোডঃ

//Weighted graph
//Author: Milon

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    int n;
    cout<<"Enter the number of nodes: ";
    cin>>n;
    int list[n][n];

    //Initialize
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            list[i][j]=false;
    cout<<"Enter an edge(start_node< >end_node< >weight)"<<endl;
    cout<<"Press (0 0 0) to end:"<<endl;

    //Making graph
    while(true){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==0 && b==0 && c==0)
            break;
        if(a>n || b>n || a<=0 || b<=0)
            cout<<"Invalid input"<<endl;
        else{
            list[a-1][b-1]=c;
            //list[b-1][a-1]=true;      //for undirected weighted graph
            }
        }
    cout<<endl;

    //Print adjacency matrix
    cout<<"Adjacency matrix:"<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            printf("%4d",list[i][j]);
        cout<<endl;
        }
    return 0;
    }

ডাটা স্ট্রাকচারঃ Adjacency List


গ্রাফের নোডের সংখ্যা যদি অনেক বেশী হয়, তখন Adjacency Matrix ব্যবহার করে গ্রাফ তৈরী করা অসুবিধাজনক। সেক্ষেত্রে Linked List ব্যবহার করে গ্রাফ তৈরী করা হয়। গ্রাফের এই ধরনের উপস্থাপনাকে Adjacency List বলে।

কোডঃ

//Adjacency list
//Author: Milon

#include<iostream>
#include<cstdlib>
using namespace std;

struct list{
    int val;
    struct list *next;
    };

struct list head[6];

int main(){
    list *ptr,*newnode;
    int data[14][2] = {{1,2},{2,1},{1,5},{5,1},{2,3},{3,2},{2,4},
                       {4,2},{3,4},{4,3},{3,5},{5,3},{4,5},{5,4}};

    //Adjacency list creation
    cout<<"The adjacent list of the graph : "<<endl;
    for(int i=1;i<6;i++){
        head[i].val=i;
        head[i].next=NULL;
        cout<<"Vertix "<<i<<" => ";
        ptr=&(head[i]);
        for(int j=0;j<14;j++){
            if(data[j][0]==i){
                newnode=new list();
                newnode->val=data[j][1];
                newnode->next=NULL;
                while(ptr!=NULL)
                   ptr=ptr->next;
                ptr=newnode;
                cout<<"["<<newnode->val<<"] ";
                }
            }
        cout<<endl;
        }
    return 0;
    }