Skip to content

Instantly share code, notes, and snippets.

@yoh2

yoh2/takahashi_num_1_18.c

Last active Aug 29, 2015
Embed
What would you like to do?
1〜18桁の高橋の数 (http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6) を求める。力技の割には意外と速い。
// 1桁〜18桁までの高橋の数を求める。
// 高橋の数 : http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6
#include <stdio.h>
#include <stdbool.h>
// 高橋の数を格納する型。
typedef long long num_t;
#define PRId_num_t "lld"
// 自然数から各桁を構成する数字を数える。
// counts[n] : n の出現数
void count_digits(num_t n, int counts[restrict static 10])
{
for(size_t i = 0; i < 10; i++)
{
counts[i] = 0;
}
while(n > 0)
{
counts[n % 10]++;
n /= 10;
}
}
// counts から構成できる最大の自然数を返す。
// counts[n] : n の出現数
num_t counts_to_max(const int counts[restrict static 10])
{
num_t n = 0;
for(int i = 9; i >= 0; i--)
{
for(int j = 0; j < counts[i]; j++)
{
n = n * 10 + i;
}
}
return n;
}
// counts から構成できる最小の自然数を返す。
// ここで、最上位桁は0以外となるようにする (counts[0]以外が0の場合を除く)
// c
num_t counts_to_min(const int counts[restrict static 10])
{
num_t n = 0;
// minimum digits other than 0
int min_dig = 0;
for(int i = 1; i < 10; i++)
{
if(counts[i] > 0)
{
min_dig = i;
break;
}
}
n = min_dig;
for(int i = 0; i < 10; i++)
{
int c = (i == min_dig)? counts[i] - 1: counts[i];
for(int j = 0; j < c; j++)
{
n = n * 10 + i;
}
}
return n;
}
bool are_same_counts(const int c1[restrict static 10], const int c2[restrict static 10])
{
for(int i = 0; i < 10; i++)
{
if(c1[i] != c2[i])
{
return false;
}
}
return true;
}
// counts から構成できる高橋の数があればその数、なければ (num_t)-1。
// counts[n] : n の出現数
num_t takahashi_num(const int counts[restrict static 10])
{
num_t min = counts_to_min(counts);
num_t max = counts_to_max(counts);
num_t diff = max - min;
int diff_counts[10];
count_digits(diff, diff_counts);
if(are_same_counts(counts, diff_counts))
{
return diff;
}
else
{
return (num_t)-1;
}
}
// counts[index] から counts[9] の合計が sum となるような
// 全パターン (各要素は0以上) に対して callback を呼び出す。
void enum_sets(
int counts[restrict static 10],
int sum, int index,
void (*callback)(const int counts[restrict static 10]))
{
if(sum == 0)
{
for(int i = index; i < 10; i++)
{
counts[i] = 0;
}
callback(counts);
}
else if(index == 9)
{
counts[index] = sum;
callback(counts);
}
else
{
for(int i = 0; i <= sum; i++)
{
counts[index] = i;
enum_sets(counts, sum - i, index + 1, callback);
}
}
}
void callback(const int counts[restrict static 10])
{
num_t t = takahashi_num(counts);
if(t != (num_t)-1)
{
printf("%"PRId_num_t"\n", t);
}
}
int main(void)
{
int counts[10];
// 1 桁から 18 桁まで。
for(int i = 1; i <= 18; i++)
{
enum_sets(counts, i, 0, callback);
}
return 0;
}
// 1桁〜18桁までの高橋の数を求める。
// 高橋の数 : http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6
// 高橋の数が 9 の倍数であるという性質を利用して枝刈りを行っている。
#include <stdio.h>
#include <stdbool.h>
// 高橋の数を格納する型。
typedef long long num_t;
#define PRId_num_t "lld"
// 自然数から各桁を構成する数字を数える。
// counts[n] : n の出現数
void count_digits(num_t n, int counts[restrict static 10])
{
for(size_t i = 0; i < 10; i++)
{
counts[i] = 0;
}
while(n > 0)
{
counts[n % 10]++;
n /= 10;
}
}
// counts から構成できる最大の自然数を返す。
// counts[n] : n の出現数
num_t counts_to_max(const int counts[restrict static 10])
{
num_t n = 0;
for(int i = 9; i >= 0; i--)
{
for(int j = 0; j < counts[i]; j++)
{
n = n * 10 + i;
}
}
return n;
}
// counts から構成できる最小の自然数を返す。
// ここで、最上位桁は0以外となるようにする (counts[0]以外が0の場合を除く)
// c
num_t counts_to_min(const int counts[restrict static 10])
{
num_t n = 0;
// minimum digits other than 0
int min_dig = 0;
for(int i = 1; i < 10; i++)
{
if(counts[i] > 0)
{
min_dig = i;
break;
}
}
n = min_dig;
for(int i = 0; i < 10; i++)
{
int c = (i == min_dig)? counts[i] - 1: counts[i];
for(int j = 0; j < c; j++)
{
n = n * 10 + i;
}
}
return n;
}
bool are_same_counts(const int c1[restrict static 10], const int c2[restrict static 10])
{
for(int i = 0; i < 10; i++)
{
if(c1[i] != c2[i])
{
return false;
}
}
return true;
}
// counts から構成できる高橋の数があればその数、なければ (num_t)-1。
// counts[n] : n の出現数
num_t takahashi_num(const int counts[restrict static 10])
{
num_t min = counts_to_min(counts);
num_t max = counts_to_max(counts);
num_t diff = max - min;
int diff_counts[10];
count_digits(diff, diff_counts);
if(are_same_counts(counts, diff_counts))
{
return diff;
}
else
{
return (num_t)-1;
}
}
// counts[index] から counts[9] の合計が sum となるような
// パターン (各要素は0以上) のうち、counts[i] * i の合計が 9 の倍数となる
// ものに対して callback を呼び出す。
void enum_sets(
int counts[restrict static 10],
int sum, int index, int weight_sum,
void (*callback)(const int counts[restrict static 10]))
{
if(sum == 0)
{
if(weight_sum % 9 == 0)
{
for(int i = index; i < 10; i++)
{
counts[i] = 0;
}
callback(counts);
}
}
else if(index == 9)
{
// 正確には、weight_sum + index * sum が
// 9の倍数か否かの判定だが、index * sum = 9 * sum
// は9の倍数であることが確定しているので、わざわざ
// 足して判定する必要はない。
if(weight_sum % 9 == 0)
{
counts[index] = sum;
callback(counts);
}
}
else
{
for(int i = 0; i <= sum; i++)
{
counts[index] = i;
enum_sets(counts, sum - i, index + 1, weight_sum + i * index, callback);
}
}
}
void callback(const int counts[restrict static 10])
{
num_t t = takahashi_num(counts);
if(t != (num_t)-1)
{
printf("%"PRId_num_t"\n", t);
}
}
int main(void)
{
int counts[10];
// 1 桁から 18 桁まで。
for(int i = 1; i <= 18; i++)
{
enum_sets(counts, i, 0, 0, callback);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment