C++练习三（poj练习）

1. poj.org的1003题

题目

• Description
  How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We’re assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + … + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.
• Input
  The input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floating-point number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.
• Output
  For each test case, output the minimum number of cards necessary to achieve an overhang of at least c card lengths. Use the exact output format shown in the examples.
  Sample Input

1.00
3.71
0.04
5.19
0.00

• Sample Output
  3 card(s)
  61 card(s)
  1 card(s)
  273 card(s)

代码

#include<iostream> 
using namespace std;

int text(double a)
{
	double n=0,m=2;
	int index=0;
	while(n<a)
	{
		n=n+1/m;
		m=m+1;
		index=index+1;
	}	
	return index;
}
void card()
{
	double a;
	int b[10],n=0;
	while(cin>>a)
	{
		if(a==0) break;
		b[n]=text(a);
		n++;	
	}	
	for(int i=0;i<n;i++)
	cout<<b[i]<<" card(s)"<<endl;
}

int main()
{
	card();
}

---

2. poj.org的1005题

题目：

• Description
  Fred Mapper is considering purchasing some land in Louisiana to build his house on. In the process of investigating the land, he learned that the state of Louisiana is actually shrinking by 50 square miles each year, due to erosion caused by the Mississippi River. Since Fred is hoping to live in this house the rest of his life, he needs to know if his land is going to be lost to erosion.
  After doing more research, Fred has learned that the land that is being lost forms a semicircle. This semicircle is part of a circle centered at (0,0), with the line that bisects the circle being the X axis. Locations below the X axis are in the water. The semicircle has an area of 0 at the beginning of year 1. (Semicircle illustrated in the Figure.)

• Input
  The first line of input will be a positive integer indicating how many data sets will be included (N). Each of the next N lines will contain the X and Y Cartesian coordinates of the land Fred is considering. These will be floating point numbers measured in miles. The Y coordinate will be non-negative. (0,0) will not be given.

• Output
  For each data set, a single line of output should appear. This line should take the form of: “Property N: This property will begin eroding in year Z.” Where N is the data set (counting from 1), and Z is the first year (start from 1) this property will be within the semicircle AT THE END OF YEAR Z. Z must be an integer. After the last data set, this should print out “END OF OUTPUT.”

• Sample Input
  2

1.0 1.0
25.0 0.0

• Sample Output
  Property 1: This property will begin eroding in year 1.
  Property 2: This property will begin eroding in year 20.
  END OF OUTPUT.

代码：

#include<iostream>
#include<cmath>
#define pi 3.1415962
using namespace std;
int radius(double a,double b)
{
	double r=0,R=0;
	int n=0;
	if(b<0)
	cout<<"error";
	r=sqrt(fabs(a*a+b*b));
	while(R<=r)
	{
		n++;
		R=sqrt(fabs(2*(50*n)/pi));	
	}
	return n;
}
void erosion()
{
	double x,y;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x>>y;
		cout<<"Property "<<i+1<<": This property will begin eroding in year "<<radius(x,y)<<"."<<endl;
	}
	cout<<"END OF OUTPUT.";
}

int main()
{
	erosion();
	return 0;
}

---

2. poj.org的1007题

题目：

• Description
  One measure of unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequenceDAABEC’’, this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequenceZWQM’’ has 6 inversions (it is as unsorted as can be—exactly the reverse of sorted).
  You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of sortedness'', frommost sorted’’ to ``least sorted’’. All the strings are of the same length.
• Input
  The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.
• Output
  Output the list of input strings, arranged from most sorted'' toleast sorted’’. Since two strings can be equally sorted, then output them according to the orginal order.
• Sample Input
  10 6
  AACATGAAGG
  TTTTGGCCAA
  TTTGGCCAAA
  GATCAGATTT
  CCCGGGGGGA
  ATCGATGCAT
• Sample Output
  CCCGGGGGGA
  AACATGAAGG
  GATCAGATTT
  ATCGATGCAT
  TTTTGGCCAA
  TTTGGCCAAA

代码：

#include<iostream>
#include<string>
#define max 100
using namespace std;

void DNA_sorting()
{
	int n,m,sorte[max],value=0;
	char str[max][max],t[max];
	cin>>m>>n;
	
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	  cin>>str[i][j];
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			for(int k=j+1;k<m;k++)
			{
				if(str[i][j]>str[i][k])
				value++;	
			}	
		}
		sorte[i]=value;
		value=0;
	}
	
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(sorte[i]>sorte[j])
			{
					for(int l=0;l<m;l++)
					{
						t[l]=str[i][l];
						str[i][l]=str[j][l];
						str[j][l]=t[l];
					}
				    value=sorte[i];
				    sorte[i]=sorte[j];
				    sorte[j]=value;
				    
			}	
		}
		
	}
	for(int i=0;i<n;i++)
	{
	for(int j=0;j<m;j++)
	cout<<str[i][j];
	cout<<endl;
	}	
} 
int main()
{
	DNA_sorting();
	return 0;
}