※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「倍数の判定法」の編集履歴(バックアップ)一覧に戻る

倍数の判定法 - (2012/12/06 (木) 16:54:46) の最新版との変更点

追加された行は青色になります。

削除された行は赤色になります。

 マスターオブ整数論 大学への数学
 
 *問い9-1
 有る4桁の数abcdを9倍すると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の各桁並べ替えてできる整数のうち11で割り切れるものを答えよ。
 
  #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か6だけからなり36の倍数となる数を求めよ。
 
 幅優先探索してみたけどコードが膨らみまくる。
 なんかもうちょっと賢い解法がありそう。
 
 
  #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が30桁並ぶ数の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の倍数になるようにせよ。
-渡された文字列が99の倍数であるものを探索する関数を書いてみました。
+渡された文字列に数字を代入して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);
  }