「倍数の判定法」の編集履歴（バックアップ）一覧はこちら
「倍数の判定法」(2012/12/06 (木) 16:57:13) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
マスターオブ整数論 大学への数学
*問い9-1
有る４桁の数abcdを９倍するとdcbaになった。この数を求めよ。
#include<stdio.h>
int main(){
int base=1009;
for(int i=0;i<20;i++){
int t1=base+i;
int t2=t1*9;
int t3=0;
for(int i=0;i<4;i++){
t3*=10;
t3+=t2%10;
t2/=10;
}
if(t1==t3)printf("(%d %d)",t1,t1*9);
}
}
*問い9-2
1234の各桁並べ替えてできる整数のうち１１で割り切れるものを答えよ。
#include<stdio.h>
int ans=0;
bool spents[5]={false,false,false,false,false};
int saiki(int mul,int n){
if(mul==0){
if(n%11==0){
ans++;
printf("%d ",n);
}
}else{
for(int i=1;i<=4;i++){
if(spents[i]==false){
spents[i]=true;
saiki(mul/10,n+mul*i);
spents[i]=false;
}
}
}
}
int main(){
saiki(1000,0);
printf("%d",ans);
}
*問い9-3
手で丁寧に解く問題なので割愛。
*問い9-4
各桁の数字が7か６だけからなり３６の倍数となる数を求めよ。
幅優先探索してみたけどコードが膨らみまくる。
なんかもうちょっと賢い解法がありそう。
#include<stdio.h>
#include<map>
#include<string>
int main(){
std::map<std::string,int> memo,next;
std::map<std::string,int>::iterator it;
memo["76"]=76%36;
std::string ansStr="",str;
while(ansStr==""){
for(it=memo.begin();it!=memo.end();it++){
str=(*it).first;
int num=(*it).second;
num=(num+6)%9;
str="6"+str;
if(num==0&&(ansStr==""||ansStr>str)){
ansStr=str;
break;
}
next[str]=num;
str=(*it).first;
num=(*it).second;
str="7"+str;
num=(num+7)%9;
if(num==0&&(ansStr==""||ansStr>str)){
ansStr=str;
}
next[str]=num;
}
memo.clear();
memo.insert(next.begin(),next.end());
next.clear();
}
printf("%s",ansStr.c_str());
}
*問い9-5
n=9、、、9が３０桁並ぶ数のn^5の各桁の和をA、Aの各桁の和をB、Bの各桁の和を足したものをC、Cを求めよ。
とりあえず賢い方法を思いつかなかったのでLispで力技で計算してみました。
Aの各桁の和を求めてみました。
何かF1エンジンを使って自転車を走らすような間抜けなコードを書いてるような気分になります。
(defun calc (n)
(let ((re 0))
(while (< 0 n)
(setq re (+ re (mod n 10))
n (truncate (/ n 10))))
re))
calc
(calc (expt (- (expt 10 30) 1) 5))
810
*問い9-6
7？4281？071の？を埋めて99の倍数になるようにせよ。
渡された文字列が９９の倍数であるものを探索する関数を書いてみました。
#include<stdio.h>
void saiki(char* num,int p,int sum9,int sum11){
if(num[p]=='\0'){
if(sum9%9==0&&sum11%11==0){
printf("%s\n",num);
}
}else{
int c=num[p]-'0';
int sig=p%2==0?1:-1;
if(0<=c&&c<=9){
saiki(num,p+1,sum9+c,sum11+c*sig);
}else{
for(int i='0';i<='9';i++){
if(p==0&&i=='0')continue;
num[p]=i;
c=i-'0';
saiki(num,p+1,sum9+c,sum11+c*sig);
}
num[p]='?';
}
}
}
int main(){
saiki("7?4281?071",0,0,0);
}
マスターオブ整数論 大学への数学
*問い9-1
有る４桁の数abcdを９倍するとdcbaになった。この数を求めよ。
#include<stdio.h>
int main(){
int base=1009;
for(int i=0;i<20;i++){
int t1=base+i;
int t2=t1*9;
int t3=0;
for(int i=0;i<4;i++){
t3*=10;
t3+=t2%10;
t2/=10;
}
if(t1==t3)printf("(%d %d)",t1,t1*9);
}
}
*問い9-2
1234の各桁並べ替えてできる整数のうち１１で割り切れるものを答えよ。
#include<stdio.h>
int ans=0;
bool spents[5]={false,false,false,false,false};
int saiki(int mul,int n){
if(mul==0){
if(n%11==0){
ans++;
printf("%d ",n);
}
}else{
for(int i=1;i<=4;i++){
if(spents[i]==false){
spents[i]=true;
saiki(mul/10,n+mul*i);
spents[i]=false;
}
}
}
}
int main(){
saiki(1000,0);
printf("%d",ans);
}
*問い9-3
手で丁寧に解く問題なので割愛。
*問い9-4
各桁の数字が7か６だけからなり３６の倍数となる数を求めよ。
幅優先探索してみたけどコードが膨らみまくる。
なんかもうちょっと賢い解法がありそう。
#include<stdio.h>
#include<map>
#include<string>
int main(){
std::map<std::string,int> memo,next;
std::map<std::string,int>::iterator it;
memo["76"]=76%36;
std::string ansStr="",str;
while(ansStr==""){
for(it=memo.begin();it!=memo.end();it++){
str=(*it).first;
int num=(*it).second;
num=(num+6)%9;
str="6"+str;
if(num==0&&(ansStr==""||ansStr>str)){
ansStr=str;
break;
}
next[str]=num;
str=(*it).first;
num=(*it).second;
str="7"+str;
num=(num+7)%9;
if(num==0&&(ansStr==""||ansStr>str)){
ansStr=str;
}
next[str]=num;
}
memo.clear();
memo.insert(next.begin(),next.end());
next.clear();
}
printf("%s",ansStr.c_str());
}
*問い9-5
n=9、、、9が３０桁並ぶ数のn^5の各桁の和をA、Aの各桁の和をB、Bの各桁の和を足したものをC、Cを求めよ。
とりあえず賢い方法を思いつかなかったのでLispで力技で計算してみました。
Aの各桁の和を求めてみました。
何かF1エンジンを使って自転車を走らすような間抜けなコードを書いてるような気分になります。
(defun calc (n)
(let ((re 0))
(while (< 0 n)
(setq re (+ re (mod n 10))
n (truncate (/ n 10))))
re))
calc
(calc (expt (- (expt 10 30) 1) 5))
810
*問い9-6
7？4281？071の？を埋めて99の倍数になるようにせよ。
渡された文字列に数字を代入して９９の倍数になるものを探索する関数を書いてみました。
#include<stdio.h>
void saiki(char* num,int p,int sum9,int sum11){
if(num[p]=='\0'){
if(sum9%9==0&&sum11%11==0){
printf("%s\n",num);
}
}else{
int c=num[p]-'0';
int sig=p%2==0?1:-1;
if(0<=c&&c<=9){
saiki(num,p+1,sum9+c,sum11+c*sig);
}else{
for(int i='0';i<='9';i++){
if(p==0&&i=='0')continue;
num[p]=i;
c=i-'0';
saiki(num,p+1,sum9+c,sum11+c*sig);
}
num[p]='?';
}
}
}
int main(){
saiki("7?4281?071",0,0,0);
}
