プロジェクトオイラー問155

Problem 155 「キャパシタ回路の数え上げ」 †
静電容量が等しい理想的なキャパシタのみを使った電気回路がある.

複数のキャパシタを直列または並列に接続してサブユニットを形成し, そのサブユニットを他のキャパシタやサブユニットと直列または並列に接続してより大きなサブユニットを形成し, そのようにして最終的な回路を形成する.

この単純な手続きをn個以下の理想的なキャパシタに適用し, 全体の静電容量が異なる複数の回路を構成することができる.

上記条件で18個までのキャパシタを使ったときに作り出せる静電容量は何種類か・



解法
定義通りに実装するだけの実装ゲームで簡単です。
2013年の日本で買える廉価パソコンで計算したところ計算時間20秒で答えが出ました。
1分ルールは少し守れてないようです。

サブユニットという条件をなくして好き放題に接続できるとすると難しくなるかもしれません。
所でキャパシタってなんでしょうか?
電気は乾電池を入れたら動く、コンセントをつないだら動く以上の教育を受けてないので結構謎です。




#include<stdio.h>
#include<set>
#include<iostream>

__int64 gcd ( __int64 a, __int64 b )
{
 __int64 c;
 while ( a != 0 ) {
     c = a; a = b%a;  b = c;
  }
  return b;
}

struct E{
	__int64 u,d;
	bool operator<(const E& e1)const{
		if(u!=e1.u)return u<e1.u;
		return d<e1.d;
	}
	E add(E& e1){
		E e2;
		__int64 u1=u*e1.d+e1.u*d;
		__int64 d1=d*e1.d;
		__int64 g=gcd(u1,d1);
		e2.u=u1/g;
		e2.d=d1/g;
		return e2;
	}
	E add2(E &e1){
		E e3=add(e1);
		E e4;
		e4.u=u*e1.u;
		e4.d=d*e1.d;
		__int64 g=gcd(e4.u,e4.d);
		e4.u/=g;
		e4.d/=g;
		E e5;
		e5.u=e4.u*e3.d;
		e5.d=e4.d*e3.u;
		g=gcd(e5.u,e5.d);
		e5.u/=g;
		e5.d/=g;
		return e5;
	}
};


int main(){
	E e1,e2,e3;
	e1.u=60;
	e1.d=1;
	
	std::set<E> sets[19],all;
	sets[1].insert(e1);
	all.insert(e1);
	
	for(int i=2;i<=18;i++){
		for(int j=1;j*2<=i;j++){
			int k=i-j;
			std::set<E>::iterator it,it2;
			for(it=sets[j].begin();it!=sets[j].end();it++){
				for(it2=sets[k].begin();it2!=sets[k].end();it2++){
					E e1=(*it);
					E e2=(*it2);
					sets[i].insert(e1.add(e2));
					sets[i].insert(e1.add2(e2));
				}
			}
		}
		all.insert(sets[i].begin(),sets[i].end());
		std::cout<<i<<" "<<all.size()<<"\n";
	}
	std::cout<<"ans="<<all.size()<<"\n";
}
最終更新:2016年02月07日 06:39