４つの数字の部分和、１０になるかチェックするiPhoneアプリのサンプルコードを描いてみます。
#import “ViewController.h”
#include <memory>
#include <vector>
#define MAX_N 10
using namespace std;
class SubsetSumChecker {
public:
bool check(int[], int, int);
private:
int a[MAX_N];
int n, k;
bool dfs(int, int);
};
bool SubsetSumChecker::check(int elements[], int size, int number) {
for (int i=0; i<size; i++) {
a[i] = elements[i];
}
n = size;
k = number;
return dfs(0, 0);
};
bool SubsetSumChecker::dfs(int i, int sum) {
if (i == n) return sum == k;
if (dfs(i + 1, sum)) return true;
if (dfs(i + 1, sum + a[i])) return true;
return false;
}
@interface ViewController () {
int elements[5][4];
}
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
// create subset
for (int i=0; i<5; i++) {
vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9};
UIView *bar = [[UIView alloc] initWithFrame:CGRectMake(10, 50 + i * 60, CGRectGetMaxX(self.view.bounds) – 20, 50)];
bar.tag = i + 1;
bar.backgroundColor = [UIColor colorWithHue:0.1 * i saturation:0.6 brightness:1 alpha:1];
[self.view addSubview:bar];
for (int j=0; j<4; j++) {
int random = arc4random() % v.size();
elements[i][j] = v[random];
v.erase(v.begin() + random);
UILabel *num = [[UILabel alloc] init];
num.font = [UIFont boldSystemFontOfSize:20];
num.text = [NSString stringWithFormat:@”%d”, elements[i][j]];
[num sizeToFit];
num.center = CGPointMake(j * 60 + 50, 75 + i * 60);
[self.view addSubview:num];
}
}
// label
UILabel *l = [[UILabel alloc] init];
l.text = @”subset sum —> 10?”;
l.font = [UIFont systemFontOfSize:25];
[l sizeToFit];
l.center = CGPointMake(CGRectGetMidX(self.view.bounds), CGRectGetMaxY(self.view.bounds) – 100);
[self.view addSubview:l];
UIButton *btn = [UIButton buttonWithType:UIButtonTypeSystem];
[btn setTitle:@”check” forState:UIControlStateNormal];
[btn sizeToFit];
btn.center = CGPointMake(CGRectGetMidX(self.view.bounds), 380);
[self.view addSubview:btn];
[btn addTarget:self action:@selector(check) forControlEvents:UIControlEventTouchUpInside];
}
– (void)check {
shared_ptr<SubsetSumChecker> cppClass(new SubsetSumChecker());
for (int i=0; i<5; i++) {
UILabel *answer = [[UILabel alloc] init];
answer.font = [UIFont boldSystemFontOfSize:30];
if (cppClass->check(elements[i], 4, 10)) {
answer.textColor = [UIColor blueColor];
answer.text = @”OK”;
} else {
answer.textColor = [UIColor redColor];
answer.text = @”NG”;
}
[answer sizeToFit];
answer.center = CGPointMake(CGRectGetMaxX(self.view.bounds) – 60, 75 + i * 60);
[self.view insertSubview:answer atIndex:0];
UIView *bar = [self.view viewWithTag:i + 1];
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(i * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
[UIView animateWithDuration:0.5 animations:^{
bar.center = CGPointMake(bar.center.x – 80, bar.center.y);
}];
});
}
}
@end