[5 Kornsrikranet] ฝึกทำโจทย์ Data Structures and Algorithms – Tree/Sorting/Graph

R 8-2

คำอธิบายการทำงานของโปรแกรม
เป็นโปรแกรมการทำงานหาของ Depth สูงสุดของ Node ที่เกิดขึ้น หรือ การหา parent ของ แต่ละโหนดที่เกินออกมา

C 8-59



คำอธิบายการทำงานของโปรแกรม
โปรแกรมจะทำการวัดระยะความห่างระหว่างโหนด 2 โหนด ว่า ห่างกันเท่าไร

R 12.16

คำอธิบายการทำงานของโปรแกรม

โปรแกรมจะทำการรับค่ามา n จำนวน หลังจากนั้นโปรแกรมจะทำการ แยก ออกเป็น 2 ส่วนเท่าๆกัน แล้วจัดค่าครั้งแรก หลังจากนั้นโปรแกรมจะทำการร่วมค่าโดยจัดจากน้อยไปมากให้เรียบร้อย
C 12.39

#include<iostream>
using namespace std;
 
// A function to do counting sort of arr[] according to
// the digit represented by exp.
int countSort(int arr[], int n, int exp)
{
 
    int output[n]; // output array
    int i, count[n] ;
    for (int i=0; i < n; i++)
       count[i] = 0;
 
    // Store count of occurrences in count[]
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%n ]++;
 
    // Change count[i] so that count[i] now contains actual
    // position of this digit in output[]
    for (i = 1; i < n; i++)
        count[i] += count[i - 1];
 
    // Build the output array
    for (i = n - 1; i >= 0; i--)
    {
        output[count[ (arr[i]/exp)%n] - 1] = arr[i];
        count[(arr[i]/exp)%n]--;
    }
 
    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to curent digit
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}
 
 
// The main function to that sorts arr[] of size n using Radix Sort
void sort(int arr[], int n)
{
    // Do counting sort for first digit in base n. Note that
    // instead of passing digit number, exp (n^0 = 1) is passed.
    countSort(arr, n, 1);
 
    // Do counting sort for second digit in base n. Note that
    // instead of passing digit number, exp (n^1 = n) is passed.
    countSort(arr, n, n);
}
 
// A utility function to print an array
void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// Driver program to test above functions
int main()
{
    // Since array size is 7, elements should be from 0 to 48
    int arr[] = {40, 12, 45, 32, 33, 1, 22};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Given array is n";
    printArr(arr, n);
 
    sort(arr, n);
 
    cout << "nSorted array is n";
    printArr(arr, n);
    return 0;
}

Answer

Given array is
40 12 45 32 33 1 22
Sorted array is
1 12 22 32 33 40 45

อธิบายการทำงานของโปรแกรม
โปรแกรมจะทำการรับค่าจาก CMD และแสดงค่าออกทางหน้าจอ การค่าที่ไม่ได้เรียงกันมาจากน้อยไปมาก หลังจากผ่านกระบวนการการทำงานของโปรแกรม โปรแกรมจะจัดเรียงข้อมูลจากน้อยไปมากให้เรียบร้อย
R 14.30

อธิบายการทำงานของโปรแกรม
โปรแกรมจะทำการตรวจสอบและเรียงค่าโหนดจาก โหนด บนสุด ไป โหนดซ้าย ไปโหนดขวา และเรียงไปจนกระทั่งถึงโหนดสุดท้าย
C 14.66

 

# Boruvka's algorithm to find Minimum Spanning
# Tree of a given connected, undirected and weighted graph
 
from collections import defaultdict
 
#Class to represent a graph
class Graph:
 
    def __init__(self,vertices):
        self.V= vertices #No. of vertices
        self.graph = [] # default dictionary to store graph
         
  
    # function to add an edge to graph
    def addEdge(self,u,v,w):
        self.graph.append([u,v,w])
 
    # A utility function to find set of an element i
    # (uses path compression technique)
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])
 
    # A function that does union of two sets of x and y
    # (uses union by rank)
    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
 
        # Attach smaller rank tree under root of high rank tree
        # (Union by Rank)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        #If ranks are same, then make one as root and increment
        # its rank by one
        else :
            parent[yroot] = xroot
            rank[xroot] += 1
 
    # The main function to construct MST using Kruskal's algorithm
    def boruvkaMST(self):
        parent = []; rank = []; 
 
        # An array to store index of the cheapest edge of
        # subset. It store [u,v,w] for each component
        cheapest =[]
 
        # Initially there are V different trees.
        # Finally there will be one tree that will be MST
        numTrees = self.V
        MSTweight = 0
 
        # Create V subsets with single elements
        for node in range(self.V):
            parent.append(node)
            rank.append(0)
            cheapest =[-1] * self.V
     
        # Keep combining components (or sets) until all
        # compnentes are not combined into single MST
 
        while numTrees > 1:
 
            # Traverse through all edges and update
               # cheapest of every component
            for i in range(len(self.graph)):
 
                # Find components (or sets) of two corners
                # of current edge
                u,v,w =  self.graph[i]
                set1 = self.find(parent, u)
                set2 = self.find(parent ,v)
 
                # If two corners of current edge belong to
                # same set, ignore current edge. Else check if 
                # current edge is closer to previous
                # cheapest edges of set1 and set2
                if set1 != set2:     
                     
                    if cheapest[set1] == -1 or cheapest[set1][2] > w :
                        cheapest[set1] = [u,v,w] 
 
                    if cheapest[set2] == -1 or cheapest[set2][2] > w :
                        cheapest[set2] = [u,v,w]
 
            # Consider the above picked cheapest edges and add them
            # to MST
            for node in range(self.V):
 
                #Check if cheapest for current set exists
                if cheapest[node] != -1:
                    u,v,w = cheapest[node]
                    set1 = self.find(parent, u)
                    set2 = self.find(parent ,v)
 
                    if set1 != set2 :
                        MSTweight += w
                        self.union(parent, rank, set1, set2)
                        print ("Edge %d-%d with weight %d included in MST" % (u,v,w))
                        numTrees = numTrees - 1
             
            #reset cheapest array
            cheapest =[-1] * self.V
 
             
        print ("Weight of MST is %d" % MSTweight)
                           
 
     
g = Graph(4)
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
 
g.boruvkaMST()
 
#This code is contributed by Neelam Yadav

อธิบายการทำงานของโปรแกรม
โปรแกรมจะทำการรับค่าและทำการคำนวณหาน้ำหนักทั้งหมด ของ โหนดว่ามีทั้งหมดแล้ว ระหว่าง โหนด ไปยังอีกโหนดหนึ่งแล้วจะค่า ออกมา

  •  
  •  
  •  
  •  
  •  
  •  
Kornsrikranet Paponsrub
at GlurGeek.Com

Leave a Reply