[pku]1491Pi

作者：xoyo 发布时间：April 10, 2010 分类：算法algorithm 104 Comments


【题意】



给出几个数字，求出一个数



公式如下



count=这几个数可以两两互质的对数



sum=这几个可以组成的对数



6/(pi*pi)=count/sum



【思路】



本题就是求出互质对数，然后注意下输出是精确到小数点后6位，所有的对数公式为(n*(n-1))/2



【代码】

#include <iostream>
#include <math.h>
using namespace std;

int ncheck(int x,int y)
{
	if (x%y==0)
		return y;
	return ncheck(y,x%y);
}

int check(int x,int y)
{
	if (x<y)
		return ncheck(y,x);
	return ncheck(x,y);
}

int main()
{
	int n;
	int num[50];
	int i,j;
	int sum,count;
	double pi;
	while (cin>>n)
	{
		if (n==0)
			break;
		memset(num,0,sizeof(num));
		count=0;
		for (i=0;i<n;i++)
			cin>>num[i];
		for (i=0;i<n-1;i++)
		{
			for (j=i+1;j<n;j++)
			{
				if (check(num[i],num[j])==1)
					count++;
			}
		}
		if (count==0)
			cout<<"No estimate for this data set.\n";
		else
		{
			sum = 3*n*(n-1);
			pi = double(sum)/count;
			pi = sqrt(pi);
			cout.setf(ios::fixed);
			cout.precision(6);
			cout<<pi<<endl;
		}
	}
}

标签: none

[pku]1308Is It A Tree?

作者：xoyo 发布时间：April 10, 2010 分类：算法algorithm 145 Comments


【题意】



每次输入都是一组数字，代表父节点和子节点，输入0 0代表结束，问输入的节点是否可以构成一颗树



【思路】



一棵树的判断有以下几个条件：



1、只有一个root，如果有多个则是森林



2、除root外其他的节点入度只能是1，如有其它，则不是



3、节点数-边数=1，主要是确保每一个节点只有一个父节点



PS：本题主要验证的错误有两个：



1、0 0是一颗树，因为是空树



2、1 2 2 3 3 1 5 6 0 0 是不是一颗树，但是如果用上述3个条件去验证的话它是，因为这是一个环+一个树。



【代码】

#pragma warning (disable:4786)
#include <iostream>
#include <map>
using namespace std;

int main()
{
	map<int,int> node,tree;
	map<int,int>::iterator itr;
	map<int,int>::iterator citr;
	int fnode,snode;
	int cases=0;
	int edges=0;
	bool isTree=true;
	int isRoot=0;
	int temp,root;
	while (cin>>fnode>>snode)
	{
		if (fnode==-1)
			break;
		if (fnode==0)
		{
			if (edges==0)//如果输入是0 0则是空树
				cout<<"Case "<<++cases<<" is a tree.\n";
			else
			{
				if (node.size()-edges!=1)//树->节点数-边数=1
					isTree=false;
				else
				{
					for (itr=node.begin();itr!=node.end();itr++)//验证1：是否是森林；2：节点入度是否有>1的
					{
						if ((*itr).second==0)
						{
							if (isRoot==0)
							{
								isRoot=1;
								root=(*itr).first;
							}
							else
								isRoot++;
						}
						if ((*itr).second>1)
							isTree=false;
					}
				}
				if (!isTree)
					cout<<"Case "<<++cases<<" is not a tree.\n";
				else if (isRoot!=1)
					cout<<"Case "<<++cases<<" is not a tree.\n";
				else
				{
					for (itr=tree.begin();itr!=tree.end();itr++)//验证连通性
					{
						temp=(*itr).second;
						while (temp!=root)
						{
							citr = tree.find(temp);//不停向父节点走
							temp = (*citr).second;
							if (temp==(*itr).first)//如果又转回来了，说明是环
							{
								isTree=false;
								break;
							}
						}
					}
					if (isTree)
						cout<<"Case "<<++cases<<" is a tree.\n";
					else
						cout<<"Case "<<++cases<<" is not a tree.\n";
				}
			}
			node.clear();
			tree.clear();
			edges=0;
			isTree=true;
			isRoot=0;
			continue;
		}
		edges++;
		tree.insert(pair<int,int>(snode,fnode));//插入到tree，第一个是子节点，第二个是父节点
		itr = node.find(fnode);
		if (itr==node.end())
			node.insert(pair<int,int>(fnode,0));//插入到node，第一个是父节点，第二个是入度0，如果找到了，则不做操作
		itr = node.find(snode);
		if (itr!=node.end())
			(*itr).second++;//对子节点的入度进行加一
		else
			node.insert(pair<int,int>(snode,1));//添加子节点，入度为1
	}
}

标签: none

[c#] 反射入门知识

作者：xoyo 发布时间：April 10, 2010 分类：程序设计 451 Comments


1、 什么是反射

2、 命名空间与装配件的关系

3、 运行期得到类型信息有什么用

4、 如何使用反射获取类型

5、 如何根据类型来动态创建对象

6、 如何获取方法以及动态调用方法

7、 动态创建委托

 1、什么是反射

        Reflection，中文翻译为反射。

        这是.Net中获取运行时类型信息的方式，.Net的应用程序由几个部分：‘程序集(Assembly)’、‘模块(Module)’、‘类型(class)’组成，而反射提供一种编程的方式，让程序员可以在程序运行期获得这几个组成部分的相关信息，例如：
        Assembly类可以获得正在运行的装配件信息，也可以动态的加载装配件，以及在装配件中查找类型信息，并创建该类型的实例。

Type类可以获得对象的类型信息，此信息包含对象的所有要素：方法、构造器、属性等等，通过Type类可以得到这些要素的信息，并且调用之。

MethodInfo包含方法的信息，通过这个类可以得到方法的名称、参数、返回值等，并且可以调用之。

诸如此类，还有FieldInfo、EventInfo等等，这些类都包含在System.Reflection命名空间下。
2、命名空间与装配件的关系

        很多人对这个概念可能还是很不清晰，对于合格的.Net程序员，有必要对这点进行澄清。

        命名空间类似与Java的包，但又不完全等同，因为Java的包必须按照目录结构来放置，命名空间则不需要。
        装配件是.Net应用程序执行的最小单位，编译出来的.dll、.exe都是装配件。
        装配件和命名空间的关系不是一一对应，也不互相包含，一个装配件里面可以有多个命名空间，一个命名空间也可以在多个装配件中存在，这样说可能有点模糊，举个例子：
	装配件A：
namespace   N1
{
      public   class   AC1   {…}
      public   class   AC2   {…}
}
namespace   N2
{
      public   class   AC3   {…}
      public   class   AC4{…}
}
装配件B：
namespace   N1
{
      public   class   BC1   {…}
      public   class   BC2   {…}
}
namespace   N2
{
      public   class   BC3   {…}
      public   class   BC4{…}
}

 这两个装配件中都有N1和N2两个命名空间，而且各声明了两个类，这样是完全可以的，然后我们在一个应用程序中引用装配件A，那么在这个应用程序中，我们能看到N1下面的类为AC1和AC2，N2下面的类为AC3和AC4。
        接着我们去掉对A的引用，加上对B的引用，那么我们在这个应用程序下能看到的N1下面的类变成了BC1和BC2，N2下面也一样。
        如果我们同时引用这两个装配件，那么N1下面我们就能看到四个类：AC1、AC2、BC1和BC2。
        到这里，我们可以清楚一个概念了，命名空间只是说明一个类型是那个族的，比如有人是汉族、有人是回族；而装配件表明一个类型住在哪里，比如有人住在北京、有人住在上海；那么北京有汉族人，也有回族人，上海有汉族人，也有回族人，这是不矛盾的。
        上面我们说了，装配件是一个类型居住的地方，那么在一个程序中要使用一个类，就必须告诉编译器这个类住在哪儿，编译器才能找到它，也就是说必须引用该装配件。

        那么如果在编写程序的时候，也许不确定这个类在哪里，仅仅只是知道它的名称，就不能使用了吗？答案是可以，这就是反射了，就是在程序运行的时候提供该类型的地址，而去找到它。

有兴趣的话，接着往下看吧。
3、运行期得到类型信息有什么用

        有人也许疑问，既然在开发时就能够写好代码，干嘛还放到运行期去做，不光繁琐，而且效率也受影响。

这就是个见仁见智的问题了，就跟早绑定和晚绑定一样，应用到不同的场合。有的人反对晚绑定，理由是损耗效率，但是很多人在享受虚函数带来的好处的时侯还没有意识到他已经用上了晚绑定。这个问题说开去，不是三言两语能讲清楚的，所以就点到为止了。

        我的看法是，晚绑定能够带来很多设计上的便利，合适的使用能够大大提高程序的复用性和灵活性，但是任何东西都有两面性，使用的时侯，需要再三衡量。
接着说，运行期得到类型信息到底有什么用呢？

还是举个例子来说明，很多软件开发者喜欢在自己的软件中留下一些接口，其他人可以编写一些插件来扩充软件的功能，比如我有一个媒体播放器，我希望以后可以很方便的扩展识别的格式，那么我声明一个接口：
	public   interface   IMediaFormat
{
string   Extension   {get;}
Decoder   GetDecoder();
}

这个接口中包含一个Extension属性，这个属性返回支持的扩展名，另一个方法返回一个解码器的对象（这里我假设了一个Decoder的类，这个类提供把文件流解码的功能，扩展插件可以派生之），通过解码器对象我就可以解释文件流。
那么我规定所有的解码插件都必须派生一个解码器，并且实现这个接口，在GetDecoder方法中返回解码器对象，并且将其类型的名称配置到我的配置文件里面。
这样的话，我就不需要在开发播放器的时侯知道将来扩展的格式的类型，只需要从配置文件中获取现在所有解码器的类型名称，而动态的创建媒体格式的对象，将其转换为IMediaFormat接口来使用。
 
这就是一个反射的典型应用。


4、如何使用反射获取类型

        首先我们来看如何获得类型信息。

        获得类型信息有两种方法，一种是得到实例对象

        这个时侯我仅仅是得到这个实例对象，得到的方式也许是一个object的引用，也许是一个接口的引用，但是我并不知道它的确切类型，我需要了解，那么就可以通过调用System.Object上声明的方法GetType来获取实例对象的类型对象，比如在某个方法内，我需要判断传递进来的参数是否实现了某个接口，如果实现了，则调用该接口的一个方法：
	…
public   void   Process(   object   processObj   )
{
Type   t   =   processsObj.GetType();
if(   t.GetInterface(“ITest”)   !=null   )
                    …
}
…


5、如何根据类型来动态创建对象

        System.Activator提供了方法来根据类型动态创建对象，比如创建一个DataTable：
Type   t   =   Type.GetType("System.Data.DataTable,System.Data,Version=1.0.3300.0,   Culture=neutral,   PublicKeyToken=b77a5c561934e089");
DataTable   table   =   (DataTable)Activator.CreateInstance(t);
    例二：根据有参数的构造器创建对象

namespace   TestSpace 

 {

  public   class   TestClass

      {

      private   string   _value;

       public   TestClass(string   value)  

     {

       _value=value;

       }

  }

}

…

Type   t   =   Type.GetType(“TestSpace.TestClass”);

Object[]   constructParms   =   new   object[]   {“hello”};   //构造器参数

TestClass   obj   =   (TestClass)Activator.CreateInstance(t,constructParms);

…

把参数按照顺序放入一个Object数组中即可


6、如何获取方法以及动态调用方法

namespace   TestSpace

{

      public   class   TestClass   {

          private   string   _value;

          public   TestClass()   {

          }

          public   TestClass(string   value)   {

                _value   =   value;

          }
          public   string   GetValue(   string   prefix   )   {

           if(   _value==null   )

           return   "NULL";

           else

             return   prefix+"   :   "+_value;

            }
            public   string   Value   {

set   {

_value=value;

}

get   {

if(   _value==null   )

return   "NULL";

else

return   _value;

}

            }

      }

}
        上面是一个简单的类，包含一个有参数的构造器，一个GetValue的方法，一个Value属性，我们可以通过方法的名称来得到方法并且调用之，如：
//获取类型信息

Type   t   =   Type.GetType("TestSpace.TestClass");

//构造器的参数

object[]   constuctParms   =   new   object[]{"timmy"};

//根据类型创建对象

object   dObj   =   Activator.CreateInstance(t,constuctParms);

//获取方法的信息

MethodInfo   method   =   t.GetMethod("GetValue");

//调用方法的一些标志位，这里的含义是Public并且是实例方法，这也是默认的值

BindingFlags   flag   =   BindingFlags.Public   |   BindingFlags.Instance;

//GetValue方法的参数

object[]   parameters   =   new   object[]{"Hello"};

//调用方法，用一个object接收返回值

object   returnValue   =   method.Invoke(dObj,flag,Type.DefaultBinder,parameters,null);
        属性与方法的调用大同小异，大家也可以参考MSDN
7、动态创建委托

        委托是C#中实现事件的基础，有时候不可避免的要动态的创建委托，实际上委托也是一种类型：System.Delegate，所有的委托都是从这个类派生的

        System.Delegate提供了一些静态方法来动态创建一个委托，比如一个委托：
namespace   TestSpace   {

      delegate   string   TestDelegate(string   value);

      public   class   TestClass   {

public   TestClass()   {

                  }

                  public   void   GetValue(string   value)   {

                          return   value;

                  }

        }

}
使用示例：

TestClass   obj   =   new   TestClass();
//获取类型，实际上这里也可以直接用typeof来获取类型

Type   t   =   Type.GetType(“TestSpace.TestClass”);

//创建代理，传入类型、创建代理的对象以及方法名称

TestDelegate   method   =   (TestDelegate)Delegate.CreateDelegate(t,obj,”GetValue”);
String   returnValue   =   method(“hello”);

标签: none

[pku]1731Orders

作者：xoyo 发布时间：April 9, 2010 分类：算法algorithm 530 Comments 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
	string s,temp;
	cin>>s;
	sort(s.begin(),s.end());
	temp = "";
	do{
		if (temp!=s)
			cout<<s<<endl;
		temp = s;
	}while (next_permutation(s.begin(),s.end()));
}

标签: none

[pku]1256Anagram

作者：xoyo 发布时间：April 9, 2010 分类：算法algorithm 87 Comments


【题意】



给你一个字符串，问该字符串中的所有字符共有多少中排列，将这些排列打印出来，排列按A<a<B<b。。。的顺序从小到大显示



【思路】



STL很强大，如果没有大小写的限制可以直接使用sort然后next_permutation就可以，不过因为大小写需要重新写一个比较函数，大概思路就是如果两个字符一样，直接返回，如果两个字符是大小写不同但是是同一字符，也直接返回，因为大写本身就比小写的小，其他的如果字符是大写则加32变为小写，然后再比较。


【代码】


	#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

bool compare(char x,char y)
{
	if (x==y)
		return x<y;
	if (x==y+32||y==x+32)
		return x<y;
	if (x>='A'&&x<='Z')
		x += 32;
	if (y>='A'&&y<='Z')
		y += 32;
	if (x!=y)
		return x<y;
}

int main()
{
	string s,temp;
	int n;
	cin>>n;
	while (n--)
	{
		temp="";
		cin>>s;
		sort(s.begin(),s.end(),compare);
		do{
			if (temp!=s)
			{
				cout<<s<<endl;
				temp = s;
			}
		}while (next_permutation(s.begin(),s.end(),compare));
	}
}

标签: none

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5