Untitled
unknown
plain_text
a year ago
8.2 kB
3
Indexable
//Huffman Coding - #include <iostream> #include <queue> #include <map> #include <string> using namespace std; struct Node { char ch; int freq; Node *left, *right; }; struct Compare { bool operator()(Node* a, Node* b) { return a->freq > b->freq; } }; Node* createHuffmanTree(string text) { map<char, int> freq; for (char ch : text) { freq[ch]++; } priority_queue<Node*, vector<Node*>, Compare> pq; for (auto& it : freq) { pq.push(new Node{it.first, it.second, nullptr, nullptr}); } while (pq.size() > 1) { Node* left = pq.top(); pq.pop(); Node* right = pq.top(); pq.pop(); Node* parent = new Node{'\0', left->freq + right->freq, left, right}; pq.push(parent); } return pq.top(); } void generateCodes(Node* root, string code, map<char, string>& codes) { if (root == nullptr) { return; } if (root->ch != '\0') { codes[root->ch] = code; } generateCodes(root->left, code + "0", codes); generateCodes(root->right, code + "1", codes); } int calculateTotalBits(string text, map<char, string>& codes) { int totalBits = 0; for (char ch : text) { totalBits += codes[ch].size(); } return totalBits; } int main() { string text; cout << "Enter the text: "; getline(cin, text); Node* root = createHuffmanTree(text); map<char, string> codes; generateCodes(root, "", codes); int totalBits = calculateTotalBits(text, codes); cout << "Total bits using Huffman coding is " << totalBits << endl; return 0; } ---------------------------------------------------------------------------------------------------------------------- // Insertion Sort #include <stdlib.h> #include <stdio.h> void insertionSort(int arr[], int size){ int key; for(int i =0; i < size; i++){ key = arr[i]; int j = i-1; while(j >= 0 && arr[j] > key){ arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } int main(){ int s; scanf("%d", &s); int *arr = (int *)malloc(s * sizeof(int)); for(int i = 0; i < s; i++){ scanf("%d", &arr[i]); } insertionSort(arr, s); for(int i = 0; i < s-1; i++){ printf("%d ", arr[i]); } printf("%d", arr[s-1]); } ---------------------------------------------------------------------------------------------------------------------- //Longest Common Sequence - #include <stdio.h> #include <string.h> int max(int a, int b) { return a > b ? a : b; } int longest_common_subsequence(char *text1, char *text2) { int m = strlen(text1); int n = strlen(text2); int dp[m + 1][n + 1]; for (int i = 0; i <= m; i++) { dp[i][0] = 0; } for (int j = 0; j <= n; j++) { dp[0][j] = 0; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1[i - 1] == text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } int main() { char text1[5]; scanf("%s", text1); char text2[5]; scanf("%s", text2); int lcs = longest_common_subsequence(text1, text2); printf("%d", lcs); return 0; } ---------------------------------------------------------------------------------------------------------------------- //Matrix Chain Multiplication - #include <stdio.h> #include <limits.h> int min_multiplications(int arr[], int n) { int dp[n + 1][n + 1]; int i, j, k, l; for (i = 1; i <= n; ++i) { dp[i][i] = 0; } for (l = 2; l <= n; ++l) { for (i = 1; i <= n - l + 1; ++i) { j = i + l - 1; dp[i][j] = INT_MAX; for (k = i; k < j; ++k) { int temp = dp[i][k] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j]; dp[i][j] = (dp[i][j] > temp) ? temp : dp[i][j]; } } } return dp[1][n]; } int main() { int s; scanf("%d", &s); int arr2[s]; for(int i = 0; i < s; i++){ scanf("%d", &arr2[i]); } int n2 = sizeof(arr2) / sizeof(arr2[0]) - 1; printf("%d\n", min_multiplications(arr2, n2)); return 0; } ---------------------------------------------------------------------------------------------------------------------- Sum of Subarray - #include <stdio.h> #include <limits.h> #include <stdlib.h> int max_subarray_sum(int nums[], int n, int *start_index, int *end_index) { int max_sum = INT_MIN; int current_sum = 0; int current_start = 0; for (int i = 0; i < n; ++i) { current_sum += nums[i]; if (current_sum > max_sum) { max_sum = current_sum; *start_index = current_start; *end_index = i; } if (current_sum < 0) { current_sum = 0; current_start = i + 1; } } if (max_sum == INT_MIN) { max_sum = nums[0]; *start_index = 0; *end_index = 0; for (int i = 1; i < n; ++i) { if (nums[i] > max_sum) { max_sum = nums[i]; *start_index = i; *end_index = i; } } } return max_sum; } int main() { int s; scanf("%d", &s); int *arr = (int *)malloc(s * sizeof(int)); for (int i = 0; i < s; ++i) { scanf("%d", &arr[i]); } int start_index, end_index; int max_sum = max_subarray_sum(arr, s, &start_index, &end_index); printf("["); for (int i = start_index; i <= end_index - 1 ; ++i) { printf("%d, ", arr[i]); } printf("%d", arr[end_index]); printf("]"); free(arr); return 0; } ---------------------------------------------------------------------------------------------------------------------- //Knapsack #include <stdio.h> #include <stdlib.h> struct Item { int weight; int profit; }; int compare(const void* a, const void* b) { const struct Item* item1 = (const struct Item*)a; const struct Item* item2 = (const struct Item*)b; return (double)(item2->profit / item2->weight) - (double)(item1->profit / item1->weight); } int knapsack(struct Item items[], int n, int capacity) { qsort(items, n, sizeof(struct Item), compare); // Sort items by profit/weight ratio int currentWeight = 0; int maxProfit = 0; for (int i = 0; i < n; i++) { if (currentWeight + items[i].weight <= capacity) { currentWeight += items[i].weight; maxProfit += items[i].profit; } else { // Calculate fraction of item to be included int fraction = (capacity - currentWeight) / items[i].weight; maxProfit += fraction * items[i].profit; break; } } return maxProfit; } int main() { int n; int capacity; scanf("%d", &n); scanf("%d", &capacity); struct Item items[n]; printf("Enter the weights and profits of the items:\n"); for (int i = 0; i < n; i++) { scanf("%d %d", &items[i].weight, &items[i].profit); } int maxProfit = knapsack(items, n, capacity); printf("Total Weight is: %d\n", maxProfit); printf("Maximum Profit is: %d\n", maxProfit); return 0; } KMP #include <iostream> #include <vector> using namespace std; vector<string> naiveStringMatching(const string& text, const string& pattern) { int n = text.length(); int m = pattern.length(); vector<string> matches; for (int i = 0; i <= n - m; i++) { int j = 0; while (j < m && text[i + j] == pattern[j]) { j++; } if (j == m) { matches.push_back(pattern); } } return matches; } int main() { string text, pattern; cout << ""; getline(cin, text); cout << ""; getline(cin, pattern); vector<string> result = naiveStringMatching(text, pattern); if (result.empty()) { cout << "None" << endl; } else { cout << result[0] << endl; } return 0; }
Editor is loading...
Leave a Comment