[広告]限られた試験時間90分の中で、どの問題に取り組めば、効率よく最も高い点をとれるか。

はじめに

通学時に電車で、問題形式の広告を見つけたのでプログラミングで解くことに挑戦してみました。間違っていたら、ご指摘いただきたいです。

試験内容

問題	得点	所要時間(分)
1	6	12
2	11	26
3	20	48
4	12	28
5	10	25
6	19	45
7	14	31
8	8	15

注意書き

• 「所要時間」は各問題で満点をとるために必要な時間で、部分点はないものとする。
• 試験では力をすべて出し切れるものとする。(願わくば、この広告を見た受験生も)

解き方

解き方としては、あまり利口ではありませんが、すべてのパターンを調べて(例:問題1のみ解く場合、問題1,2を解く場合 etc.)その中から、90分以内で高い点数をとれるものを見つけ出すのが良いと考えました。

問題に取り組むすべてのパターンは、設問数が8なので、符号なし8bitで扱える整数の値であると判断しました(0~255の256パターン)。一応、プログラムは、設問数がいくつでもいいように作成。(関数名が微妙...（笑）)

// Find the range of numbers that can be handled in n bits.
size_t calc_total(size_t n)
{
	size_t i;
	size_t sum;

	i = 0;
	sum = 0;
	while (i < n)
	{
		sum += pow(2, i);
		i++;
	}
	return (sum);
}

次に、256パターン(0~255)を2進数に変換する関数を作成しました。

// Convert from decimal to n-digit binary
char *convert_n_digit_binary(size_t value, size_t digit)
{
	char *array;
	size_t tmp;
	size_t i;

	array = (char *)calloc((digit + 1), sizeof(char));
	for (int i=0; i<digit; i++)
		array[i] = '0';
	i = 1;
	while (value > 0 || i <= digit)
	{
		array[digit - i] = '0' + value % 2;
		value /= 2;
		i++;
	}
	return (array);
}

arrayは、digit+1分メモリを確保していて、これは終端文字分です。また、メモリ確保は成功する前提で作成しています。(よくないですが...)

今回のデータの比較では、得点が同じ場合には、所要時間が短いものを選択するようにしています。

bool compare_pattern(t_box *target, t_box *highest)
{
	if (target->time > EXAM_TIME)
		return (false);
	if (target->score > highest->score)
		return (true);
	else if (target->score == highest->score && target->time < highest->time)
		return (true);
	return (false);
}

構造体など、他にもコードを書いているのでひとまずコードを全部だします。

calc_highest_score.c

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>

#define EXAM_TIME 90
#define Q_NUM 8

typedef struct s_box
{
	char	*binary;
	int		score;
	int		time;
}	t_box;

// prototype
void	all_free(int **data, t_box *result);
void	print_select_question(t_box *result);
bool	compare_pattern(t_box *a, t_box *b);
t_box	*calc_pattern(int **data, size_t n);
t_box	*global_search(int **data, size_t pattern);
char	*convert_n_digit_binary(size_t value, size_t digit);
size_t	calc_total(size_t n);
int		**get_input_data(int n);

void all_free(int **data, t_box *result)
{
	for (int i=0; i<Q_NUM; i++)
	{
		free(data[i]);
	}
	free(data);
	free(result);
}

void print_select_question(t_box *result)
{
	printf("Selected question : ");
	for (int i=0; i<Q_NUM; i++)
	{
		if (result->binary[i] == '1')
		{
			printf("%d", i+1);
			if (i != Q_NUM - 1)
				printf(", ");
			else
				printf("\n");
		}
	}
	printf("Score             : %d\n", result->score);
	printf("Required time     : %d\n", result->time);
}

// Assume true if the target has a higher score.
// If the scores are the same, the shorter time is better.
bool compare_pattern(t_box *target, t_box *highest)
{
	if (target->time > EXAM_TIME)
		return (false);
	if (target->score > highest->score)
		return (true);
	else if (target->score == highest->score && target->time < highest->time)
		return (true);
	return (false);
}

t_box *calc_pattern(int **data, size_t n)
{
	t_box *one_pattern;
	size_t i;

	one_pattern = (t_box *)malloc(2 * sizeof(t_box));
	one_pattern->binary = convert_n_digit_binary(n, Q_NUM);
	one_pattern->score = 0;
	one_pattern->time = 0;
	i = 0;
	while (i < Q_NUM)
	{
		if (one_pattern->binary[i] == '1')
		{
			one_pattern->score += data[i][0];
			one_pattern->time += data[i][1];
		}
		i++;
	}
	return (one_pattern);
}

// Always compare while calculating all patterns.
t_box *global_search(int **data, size_t pattern)
{
	size_t i, j;
	t_box *tmp, *highest;

	i = 0;
	while (i <= pattern)
	{
		tmp = calc_pattern(data, i);
		// printf("%s %d %d\n", tmp->binary, tmp->score, tmp->time);
		if (i == 0)
		{
			highest = tmp;
		}
		else
		{
			if (compare_pattern(tmp, highest) == true)
			{
				highest = tmp;
			}
		}
		tmp = NULL;
		free(tmp);
		i++;
	}
	return (highest);
}

// Convert from decimal to n-digit binary
char *convert_n_digit_binary(size_t value, size_t digit)
{
	char *array;
	size_t tmp;
	size_t i;

	array = (char *)calloc((digit + 1), sizeof(char));
	for (int i=0; i<digit; i++)
		array[i] = '0';
	i = 1;
	while (value > 0 || i <= digit)
	{
		array[digit - i] = '0' + value % 2;
		value /= 2;
		i++;
	}
	return (array);
}

// Find the range of numbers that can be handled in n bits.
size_t calc_total(size_t n)
{
	size_t i;
	size_t sum;

	i = 0;
	sum = 0;
	while (i < n)
	{
		sum += pow(2, i);
		i++;
	}
	return (sum);
}

int **get_input_data(int n)
{
	int **data;	// data[i][0] = score, data[i][1] = time

	// allocate memory
	data = (int **)malloc(Q_NUM * sizeof(int *));
	for (int i=0; i<Q_NUM; i++)
	{
		// Have two sets of data: scores and time
		data[i] = (int *)malloc(2 * sizeof(int));
	}
	// input
	for (int i=0; i<Q_NUM; i++)
	{
		for (int j=0; j<2; j++)
		{
			scanf("%d", &data[i][j]);
		}
	}
	return (data);
}

int main(void)
{
	int **data;
	size_t total;
	t_box *result;

	data = get_input_data(Q_NUM);
	total = calc_total(Q_NUM);
	result = global_search(data, total);
	print_select_question(result);
	all_free(data, result);
	return (0);
}

一応、わかりやすくコードを書いているつもりです！（笑）
どしどしアドバイスお願いします！

ひとまず解答

Selected question : 1, 4, 7, 8
Score             : 40
Required time     : 86

この試験全然点数とれないじゃん（笑）
答えが違うのでは？と思って全パターン出力してみたのですが、正しいっぽい（笑）

今後の課題

• 全てのパターンについて考えていると設問数が増えた場合に、計算量が増えるので、改良する余地あり。
• メモリリークしているかも？

最後に

何でもいいのでアドバイスお待ちしています！