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 |
อธิบายการทำงานของโปรแกรม
โปรแกรมจะทำการรับค่าและทำการคำนวณหาน้ำหนักทั้งหมด ของ โหนดว่ามีทั้งหมดแล้ว ระหว่าง โหนด ไปยังอีกโหนดหนึ่งแล้วจะค่า ออกมา
