首页 > ACM题库 > HDU-杭电 > HDU 3429-Resistors-递归和分治-[解题报告]HOJ
2014
03-23

HDU 3429-Resistors-递归和分治-[解题报告]HOJ

Resistors

问题描述 :

Every electrical appliance (such as a light bulb) has a certain resistance. If the appliance is connected to a given voltage, the higher its resistance, the lower the current flowing through the appliance. The unit of measurement for resistance is the ohm. In order to avoid round-off errors that can affect floating-point numbers, we will use rational numbers (quotients of positive integers) to represent the resistance of an appliance numerically. There are two basic ways to connect two or more appliances into a configuration of
appliances: serially (Figure 1) or parallel (Figure 2). Two or more configurations can be further connected serially or parallel to yield another
(more complex) configuration yet, and this process of building more complex configurations from existing ones can be repeated any number of times (Figure 3). In general, a configuration is either a single appliance, or a serial connection of two or more configurations, or a parallel connection of two or more configurations. The resistance of a configuration of resistors can be computed according to the following
two rules:
1. The resistance of a serial configuration is the sum of the resistances of its component
configurations.
2. The resistance of a parallel configuration is the reciprocal of the sum of the
reciprocals of its component configurations.
Balance

In Figure 1, the resistance of the configuration is 3/2 + 3/4 + 1/4 = 5/2 ohm.In Figure 2, the resistance of the configuration is 1/(1/(3/2) + 1/(1/2) + 1/ (1/4)) = 3/20 ohm
Balance

In Figure 3, we first calculate 1/(1/(1/2) + 1/(2/3)) + 2/5 = 24/35 and 1/2 + 1/(1/(2/3) + 1/(2/5)) + 3/2 = 9/4. Adding the reciprocals of these two values and reciprocating the result, we get 72/137 ohm.
A configuration can be represented in text format.

*A single appliance is represented by the numerical value of its resistance (without enclosing parentheses).
*A configuration that is the serial connection of several configurations is represented as a list of the representations of its components, separated by the ampersand character ("&") and enclosed in a pair of parentheses.
*A configuration that is the parallel connection of several configurations is represented as a list of the representations of its components, separated by the vertical bar character ("|") and enclosed in a pair of parentheses.

Thus, figures 1, 2, and 3 are represented in text format by the respective expressions:

(3/2 & 3/4 & 1/4)
(3/2 | 1/2 | 1/4)
(((1/2 | 2/3) & 2/5) | (1/2 & (2/3 | 2/5) & 3/2))

输入:

The input consists of a number of test cases, one test case per line. Each line of the input contains a valid expression that defines a configuration according to the rules stated above. The resistance values of the appliances will be positive rational numbers, in the form NUMERATOR/DENOMINATOR. There will be one blank space on each side of every ampersand or vertical bar. There will be no other blank spaces in the expression.

输出:

The input consists of a number of test cases, one test case per line. Each line of the input contains a valid expression that defines a configuration according to the rules stated above. The resistance values of the appliances will be positive rational numbers, in the form NUMERATOR/DENOMINATOR. There will be one blank space on each side of every ampersand or vertical bar. There will be no other blank spaces in the expression.

样例输入:

15/1
(3/2 & 3/4 & 1/4)
(3/2 | 1/2 | 1/4)
((1/2 | 2/3) & 2/5)
(1/2 & (2/3 | 2/5) & 3/2)
(((1/2 | 2/3) & 2/5) | (1/2 & (2/3 | 2/5) & 3/2))

样例输出:

15/1
5/2
3/20
24/35
9/4
72/137

2009年洛矶山区域赛 中的一题

这套题可以在 http://org.coloradomesa.edu/acm/rmrc/2009/index.html 下载标程和数据

读入部分参考了:http://hi.baidu.com/czz19891012/item/c824ca83cca60be8e496e014

第一次写分数模板,还没有用其他题目测试过,可能有bug

题意:就是算电路的总电阻,&表示串联,| 表示并联

分数存储的时候要用64位整型

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <string>
using namespace std;

#define i64 __int64

class fraction
{
private:
	inline i64 Gcd (i64 x,i64 y)
	{
		return y==0?x:Gcd(y,x%y);
	}

	i64 Lcm (i64 x,i64 y)
	{
		x=x/Gcd(x,y)*y;
		if(x<0) x=-x;
		return x;
	}
public:
    i64 a,b;

    fraction () {}
    fraction (i64 x)
    {
        a=x; b=1;
    }

    fraction (i64 x,i64 y)
    {
        a=x; b=y;
        Refresh();
    }

    void Refresh ()
    {
        if (b<0) b=-b,a=-a;
        i64 k=Gcd(a,b);
        if (k<0) k=-k;
        a/=k; b/=k;
    }

	fraction Inverse () const
	{//取倒数
		return fraction (b,a);
	}

    fraction operator + (fraction p)
    {
        fraction ans;
        ans.b=Lcm(b,p.b);
        ans.a=ans.b/b*a+ans.b/p.b*p.a;
        ans.Refresh();
        return ans;
    }

    fraction operator - (fraction p)
    {
        fraction ans;
        ans.b=Lcm(b,p.b);
        ans.a=ans.b/b*a-ans.b/p.b*p.a;
        ans.Refresh();
        return ans;
    }

    fraction operator * (fraction p)
    {
        fraction ans;
        ans.a=a*p.a;
        ans.b=b*p.b;
        ans.Refresh();
        return ans;
    }

    fraction operator / (fraction p)
    {
        fraction ans;
        ans.a=a*p.b;
        ans.b=b*p.a;
        ans.Refresh();
        return ans;
    }

    bool operator < (const fraction &p) const
    {
        return a*p.b<b*p.a;
    }

    bool operator > (const fraction &p) const
    {
        return a*p.b>b*p.a;
    }

    bool operator == (const fraction &p) const
    {
        return a*p.b==b*p.a;
    }
	
	fraction operator | (fraction p)
	{//取倒相加取倒
		fraction t1=fraction (b,a);
		fraction t2=p.Inverse ();
		t1=t1+t2;
		return t1.Inverse();
	}

    void print ()
    {
        printf("%I64d/%I64d\n",a,b);
    }
};

string s;
int len;

fraction read (int &now)
{
    int fz=0,fm=0;
    int i;
    for (i=now;i<len;i++)
    {
        if (s[i]=='/') break;
        fz*=10;
        fz+=s[i]-'0';
    }
    for (i=i+1;i<len;i++)
    {
        if (isdigit(s[i]))
        {
            fm*=10;
            fm+=s[i]-'0';
        }
        else break;
    }
	fraction tmp(fz,fm);
    now=i-1;
    return tmp;
}

fraction cal (int &now)
{
    fraction ans;
    int front=-1;
    for (int i=now+1;i<len;i++)
    {
        if (s[i]=='(')
        {
            if(front==-1)
               ans=cal(i);
            else if(front==0)
                ans=ans+cal(i);
            else if(front==1)
                ans=ans|cal(i);
        }
        else if (isdigit(s[i]))
        {
            if (front==-1)
                ans=read(i);
            else if (front==0)
                ans=ans+read(i);
            else if (front==1)
                ans=ans|read(i);
        }
        else if (s[i]==')')
        {
            now=i;
            return ans;
        }
        else if (s[i]=='&')
            front=0;
        else if (s[i]=='|')
            front=1;
    }
}

int main ()
{
	while (getline(cin,s))
	{
		len=s.length();
		fraction ans;
		int flag=-1; //-1:之前没有运算符, 0:之前 &, 1:之前 |
		for (int i=0;i<len;i++)
		{
			if (s[i]=='(')
			{
				if (flag==-1)
					ans=cal(i);
				else if (flag==0)
					ans=ans+cal(i);
				else if(flag==1)
					ans=ans|cal(i);
			}
			else if (isdigit(s[i]))
			{
				if (flag==-1)
					ans=read(i);
				else if (flag==0)
					ans=ans+read(i);
				else if (flag==1) 
					ans=ans|read(i);
			}
			else if (s[i]=='&')
				flag=0;
			else if (s[i]=='|')
				flag=1;
		}
		ans.print();
	}
	return 0;
}

参考:http://blog.csdn.net/whyorwhnt/article/details/19259677


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }