分割統治法 最小値
今回は分割統治法により最小値を求めるプログラムを作成しました。
分割統治法とは、端的に説明すると細かくブロック範囲を再帰的にブロック分けしていき、
範囲を狭めた中で処理を行うアルゴリズムです。
入力例
nはデータの数
na, n2, ... nnは各データの値です。
n n1 n2 n3 n4
以下は解答例になります。
#include <stdio.h> int main(void) { int n, data[10000], i, ans; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &data[i]); } ans = divide_min(data, 0, n - 1); printf("%d", ans); return 0; } int divide_min(int data[10000], int begin, int end) { if (begin == end) { return data[begin]; } int mid, ans1, ans2; mid = (begin + end) / 2; ans1 = divide_min(data, begin, mid); ans2 = divide_min(data, mid + 1, end); if (ans1 < ans2) { return ans1; } else { return ans2; } }