E-Book How To Solve It By Computer : 4.5 Partitioning An Array.
4.5.1 :
#include <iostream>
#include <stdio.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
int n, *arr, onee = 0, twoo, threee, total = 0, maxx = -1, temp_maxx;
cin >> n;
arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
total += arr[i];
}
// O(n^2) is the following
for (int i = 1; i < n - 1; i++) {
onee += arr[i - 1];
twoo = 0;
for (int j = i + 1; j < n; j++) {
twoo += arr[j - 1];
threee = total - twoo - onee;
temp_maxx = max(max(onee, twoo), threee);
if ((temp_maxx < maxx) || (maxx == -1))
maxx = temp_maxx;
}
}
cout << maxx;
return 0;
}
4.5.2 :
Algoritma :var
A; array[1..100] of interger;
i: integer;
begin
for i:=1 to 100 do
begin
A[1]:=i;
end;
End.
4.5.3 :
#include <iostream>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
//Bucket Sort
void bucket_sort (int arr[], int n)
{
//Here range is [1,100]
int m = 101;
//Create m empty buckets
int buckets[m];
//Intialize all buckets to 0
for (int i = 0; i < m; ++i)
buckets[i] = 0;
//Increment the number of times each element is present in the input
//array. Insert them in the buckets
for (int i = 0; i < n; ++i)
++buckets[arr[i]];
//Sort using insertion sort and concatenate
for (int i = 0, j = 0; j < m; ++j)
for (int k = buckets[j]; k > 0; --k)
arr[i++] = j;
}
//Driver function to test above function
int main()
{
int input_ar[] = {10, 24, 22, 62, 1, 50, 100, 75, 2, 3};
int n = sizeof (input_ar) / sizeof (input_ar[0]);
bucket_sort (input_ar, n);
cout << "Sorted Array : " << endl;
for (int i = 0; i < n; ++i)
cout << input_ar[i] << " ";
return 0;
}
Sekian dan Terima Kasih, Semoga Bermanfaat.
Comments