オイラープロジェクト101～110 - c21coterie @ ウィキ

問い101

まずＬｉｓｐコードで問題のy=f(x)を求めました。

(defun saiki(n m sum deep)
  (if (= deep 11)
      sum
    (if (= (mod deep 2) 1) 
(saiki (* n m) m (- sum n) (+ deep 1))
      (saiki (* n m) m (+ sum n) (+ deep 1)))))
saiki
(dotimes (i 11)
  (print (saiki 1 (+ 1 i) 0 0)))

次にＣ++コードでニュートン補間を使って答えを求めました。
ニュートン補間の結果求まった値が整数になるのは中々不思議な感じです。

#include<stdio.h>
#include<iostream>
//1 683 44287 838861 8138021 51828151 247165843 954437177 3138105961 9090909091 
//式のｙ値
double y[]={1,683,44287,838861,8138021,51828151,247165843,954437177,3138105961,9090909091};
//double y[]={1,8,27,64};
double x[]={1,2,3,4,5,6,7,8,9,10};
double newton(int n,double t){
double a[20];
double w[20],s;
for(int i=0;i<n;i++){
	w[i]=y[i];
	for(int j=i-1;j>=0;j--){
		w[j]=(w[j+1]-w[j])/(x[i]-x[j]);
	}
	a[i]=w[0];
}
s=a[n-1];
for(int i=n-2;i>=0;i--){
	s=s*(t-x[i])+a[i];
}
return s;
}
int main(){
__int64 ans=1;
for(int i=2;i<10;i++){
	printf("%d %lf\n",i,newton(i,i+1));
	ans+=newton(i,i+1);
}
std::cout<<ans;
}

問い102

http://projecteuler.net/problem=102
1000個の三角形のデータが与えられるので、原点を含むものが何個あるか。
計算誤差を考えなくてすむ整数値でデータが与えられているのでとても楽な問題。
外積の概念を使って楽々アセプト。
三角形ＡＢＣを考えた時、外積ＯＡ*ＯＢ、ＯＢ*ＯＣ、ＯＣ*ＯＡの符号がそろえば原点が三角形の内部にあると判断。

#include <stdio.h>
#include<iostream>
int main(){
FILE *fp;
if((fp=fopen("triangles.txt","r"))==NULL){
	printf("fileOpenError");
	exit(EXIT_FAILURE);
}
int xs[3],ys[3],ans=0;
while(fscanf(fp,"%d,%d,%d,%d,%d,%d",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2])>0){
	int a=xs[0]*ys[1]-xs[1]*ys[0];
	int b=xs[1]*ys[2]-xs[2]*ys[1];
	int c=xs[2]*ys[0]-xs[0]*ys[2];
	ans+=((a<0&&b<0&&c<0)||(a>0&&b>0&&c>0));
}
fclose(fp);
std::cout<<ans;
}

103

http://projecteuler.net/problem=103
特殊和集合の長さ7の最適特殊和集合を求めよという問題。
とりあえず答えが見たかったのでちょっぱやで全探索コードをためしてみました。
もうちょっと賢い方法があるようです。

#include<stdio.h>

bool isOK;
int ans[7];
void check(int B,int C,int deep,int BS,int CS,int deepMax){
	if(deep==deepMax){
		if(BS==0||CS==0)return ;
		if(B==C)isOK=false;
		if(BS<CS&&B>=C)isOK=false;
 		if(BS>CS&&B<=C)isOK=false;
	}else{
		check(B+ans[deep],C,deep+1,BS+1,CS,deepMax);
		if(isOK==false)return ;
		check(B,C+ans[deep],deep+1,BS,CS+1,deepMax);
		if(isOK==false)return ;
		check(B,C,	    deep+1,BS,CS,  deepMax);
	}
}
 
void searchPerm(int deep,int old,int spents){
 	if(deep>2&&deep<6){
		isOK=true;
		check(0,0,0,0,0,deep);
		if(isOK==false){
			return ;
		}
		isOK=false;
	}
	if(deep==6&&old<spents){
		ans[6]=spents;
		isOK=true;
		check(0,0,0,0,0,7);
	}else{
		if(spents/(7-deep)+1<old)return;
		for(int i=old+1;i<spents;i++){
			ans[deep]=i;
			searchPerm(deep+1,i,spents-i);
			if(isOK==true)return ;
		}
	}
}

int main(){
	for(int i=116;i<500;i++){
		isOK=false;
		searchPerm(0,0,i);
 		if(isOK==true){
			printf("ans=");
			for(int i=0;i<7;i++)printf("%d ",ans[i]);
			printf("\n");
			break;
		}
		printf("%d\n",i);
	}
}

問い105

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20105
与えられた数字の集合が特殊和集合を満たしているか満たしているものの数を足し合わせよという問題。
組み合わせ数が少ないので全探索で求めてみました。
一瞬で答えが出ますが探索量を減らす方法はいろいろあると思います。

例えば集合を数字の大小でソートします。
集合Ｂを全探索し、残りを大きい方からＣに足していき条件を満たすか見れば多少計算量が減ります。

#include<stdio.h>
#include<vector>
bool ok;
std::vector<int> data;
void saiki(int a,int b,int acount,int bcount,int deep,int size){
if(a==b&&a!=0){
	ok=false;
	return ;
}
if(acount>bcount&&a<=b){
	ok=false;
	return ;
}else if(acount<bcount&&b<=a){
	ok=false;
	return ;
}
if(deep==size){
	return ;
}
saiki(a+data[deep],b,acount+1,bcount,deep+1,size);//集合aに足す
if(ok==false)return;
saiki(a,b+data[deep],acount,bcount+1,deep+1,size);//集合ｂに足す
if(ok==false)return ;
saiki(a,b,acount,bcount,deep+1,size);//どちらにも足さない
}
int check(){
ok=true;
int sum=0,a;
char c;
data.clear();
while(1){
	scanf("%d%c",&a,&c);
	data.push_back(a);
	sum+=a;
	if(c=='\n')break;
}
saiki(0,0,0,0,0,data.size());
return ok*sum;
}
int main(){
int sum=0,t;
for(int i=0;i<100;i++){
	t=check();
	printf("%d\n",t);
	sum+=t;
}
printf("\nlast=%d\n",sum);
}

問い107

プリム法の問題、特筆すべきことなし。
プリム法を知らない時にプリム法と同じ方法を自分で考えついたのを思い出す。

#include<stdio.h>
#include<queue>
bool cons[41];
int gs[41][41];
int sum=0;
struct E{
int cost,no;
bool operator<(const E& e)const{
	return cost>e.cost;
}
};
void calc(){
memset(cons,false,sizeof(cons));
std::priority_queue<E> pq;
E e,next;
e.cost=e.no=0;
pq.push(e);
int m=0;
while(!pq.empty()){
	e=pq.top();
	pq.pop();
	if(cons[e.no]==true)continue;
	printf("%d,%d\n",e.no,e.cost);
	cons[e.no]=true;
	m+=e.cost;
	for(int i=0;i<40;i++){
		if(gs[e.no][i]!=-1&&cons[i]==false){
			next.no=i;
			next.cost=gs[e.no][i];
			pq.push(next);
		}
	}
}
printf("%d %d %d",sum/2,m,sum/2-m);
}
void setData(){
char c;
for(int i=0;i<40;i++){
	for(int j=0;j<40;j++){
		scanf("%d%c",&gs[i][j],&c);
		if(gs[i][j]!=-1)sum+=gs[i][j];
	}
}
printf("\nreadOK\n");
}
int main(){
setData();
calc();
}

問い109

ダーツで100ポイント未満でチェックアウトする方法はいくつあるか。
ダーツのルールを知らなかったのでルールを理解するのに時間がかかった問題。

ルールが理解出来たら後は全探索で片がつきました。

#include<stdio.h>
int noToPoint(int n){
int p;
if(n==61)p=25;
if(n==62)p=50;
if(n<61)p=((n-1)%20+1)*((n-1)/20+1);
return p;
}
int main(){
int p1,p2,ans=0;
for(int a=0;a<63;a++){
	p1=noToPoint(a);
	if(p1>=100)continue;
	for(int b=a;b<63;b++){
		p2=noToPoint(b);
		if(p1+p2>=100)continue;
		for(int p3=2;p3<41;p3+=2){
			if(p1+p2+p3>=100)break;
			ans++;
		}
		if(p1+p2+50<100)ans++;
	}
}
printf("%d\n",ans);
}