dolf

题目：
Problem Statement
????
***Note: Please keep programs under 7000 characters in length. Thank you
Class Name: SquareDigits
Method Name: smallestResult
Parameters: int
Returns: int

Define the function S(x) as the sum of the squares of the digits of x. �
For example: S(3)=3*3=9 and S(230)=2*2+3*3+0*0=13.

Define the set T(x) to be the set of unique numbers that are produced by
repeatedly applying S to x. That is: S(x), S(S(x)), S(S(S(x))), etc…
For example, repeatedly applying S to 37:
S(37)=3*3+7*7=58.�
S(58)=5*5+8*8=89.
S(89)=145.
S(145)=42.
S(42)=20.
S(20)=4.
S(4)=16.
S(16)=37.
Note this sequence will repeat so we can stop calculating now and:
T(37)={58,89,145,42,20,4,16,37}.
However, note T(x) may not necessarily contain x.

Implement a class SquareDigits, which contains a method smallestResult. The
method takes an int, n, as a parameter and returns the smallest int, x, such
that T(x) contains n.

The method signature is (be sure your method is public):
int smallestResult(int n);

TopCoder will ensure n is non-negative and is between 0 and 199 inclusive.

Examples:
If n=0: S(0) = 0, so T(0)={0}, so the method should return 0.

If n=2: T(0) through T(10) do not contain the value 2. If x=11, however:
S(11)=1*1+1*1=2, so T(11) contains 2, and the method should return 11.

If n=10: T(0) through T(6) do not contain 10. If x=7:
S(7)=49.
S(49)=97.
S(97)=130.
S(130)=10.
S(10)=1.
and it starts to repeat…
so T(7) is {49,97,130,10,1}, which contains 10, and the method should return 7.

n=1 -> x=1
n=19 -> x=133
n=85 -> x=5
n=112 -> x=2666
Definition
????
Class:
SquareDigits
Method:
smallestResult
Parameters:
int
Returns:
int
Method signature:
int smallestResult(int param0)
(be sure your method is public)
????

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

解答：

#include<iostream>
using namespace std;
const int MAXLENGTH = 1000;
class SquareDigits
{
public:
SquareDigits()
{
  sresult = 0;
  smallResult = 0;
  ti = 0;
  lengthoftresult = 0;
  xinput = 0;
  number = 0;
  for(int i=0;i<MAXLENGTH; i++)
   tresult[i]=”;
}
int s(int x)
{
  if(x<10)
   sresult += x*x;
  else
  {
   int mod = x%10;
   sresult += mod*mod;
   s(x/10);
  }
  return sresult;
}
int* t(int x)
{
  xinput = x;
  lengthoftresult = 0;
  return t1(x);
}

int* t1(int x)
{
  sresult = 0;
  if(x == 0 || x==1)
  {
   tresult[ti]=x;
   lengthoftresult++;
  }
  else
  {
   int temp = s(x);
   if(xinput != temp && ti<MAXLENGTH)
   {
    for(int i = 0; i<lengthoftresult-1;i++)
    {
     if(temp == tresult[i])
      return tresult;
    }
    tresult[ti] = temp;
    ti++;
    lengthoftresult++;
    t1(temp);
   }
   ti = 0;
  }
  return tresult;
}

int smallestResult(int n)
{
  number = n;
  int i=0;
  do
  {
   t(i);
   i++;
  }while(comparetsmall()!=true);
  smallResult = i -1 ;
  return smallResult;
}
bool comparetsmall()
{
  for(int i=0; i<lengthoftresult; i++)
  {
  �
   if(tresult[i] == number)
    return true;
  }
  return false;
}
private:
int sresult;
int tresult[MAXLENGTH];
int xinput;
int lengthoftresult;
int ti;
int smallResult;
int number;
};

void main()
{
SquareDigits sd;

int x = 0;
cout<<”Input the param of n:”<<endl;
cin>>x;
//cout<<”x is:”<<x<<endl;

int smallresult = sd.smallestResult(x);
cout<<”smallestresult is:”<<smallresult<<endl;

//sd.t(x);
}

Posted in Algorithm, TopCoder | No Comments »

在TopCoder上算法类的第一题

十月 8th, 2007 by dolf

题目：

***Note: Please keep programs under 7000 characters in length. Thank you
Class Name: HowEasy
Method Name: pointVal
Parameters: String
Returns: int

TopCoder has decided to automate the process of assigning problem difficulty
levels to problems. TopCoder developers have concluded that problem difficulty
is related only to the Average Word Length of Words in the problem statement:

If the Average Word Length is less than or equal to 3, the problem is a 250
point problem.
If the Average Word Length is equal to 4 or 5, the problem is a 500 point
problem.
If the Average Word Length is greater than or equal to 6, the problem is a 1000
point problem.

Definitions:
Token - a set of characters bound on either side by spaces, the beginning of
the input String parameter or the end of the input String parameter.
Word - a Token that contains only letters (a-z or A-Z) and may end with a
single period. A Word must have at least one letter.
Word Length - the number of letters in a Word. (NOTE: a period is NOT a letter)

The following are Words :
“ab”, “ab.”

The following are not Words :
“ab..”, “a.b”, “.ab”, “a.b.”, “a2b.”, “.”

Average Word Length - the sum of the Word Lengths of every Word in the problem
statement divided by the number of Words in the problem statement. The
division is integer division. If the number of Words is 0, the Average Word
Length is 0.

Implement a class HowEasy, which contains a method pointVal. The method takes
a String as a parameter that is the problem statement and returns an int that
is the point value of the problem (250, 500, or 1000). The problem statement
should be processed from left to right.

Here is the method signature (be sure your method is public):
int pointVal(String problemStatement);

problemStatement is a String containing between 1 and 50 letters, numbers,
spaces, or periods. TopCoder will ensure the input is valid.

Examples:

If problemStatement=”This is a problem statement”, the Average Word Length is
23/5=4, so the method should return 500.
If problemStatement=”523hi.”, there are no Words, so the Average Word Length is
0, and the method should return 250.
If problemStatement=”Implement a class H5 which contains some method.” the
Average Word Length is 38/7=5 and the method should return 500.
If problemStatement=” no9 . wor7ds he8re. hj..” the Average Word Length is 0,
and the method should return 250.
Definition
????
Class:
HowEasy
Method:
pointVal
Parameters:
string
Returns:
int
Method signature:
int pointVal(string param0)
(be sure your method is public)
????

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

其实很简单，就是让你提供一个类，然后具体功能看描述。

我巨汗，竟然折腾了1个半小时才弄出来，这题250分，我就得了76.9分，可怜，下面是解法：

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

class HowEasy
{
public:
int pointVal(string str)
{
  int point = 0;
  int awlength = 0;
  int words = 0;
  int letters = 0;
  char end = ”;
  bool flag = false;
  basic_string <char>::iterator str_Iter;
  for ( str_Iter = str.begin( ); str_Iter != str.end( ); str_Iter++ )
  {
   char temp = *str_Iter;
   if ((temp<= ‘z’&&temp>=’a')||(temp>=’A'&&temp<=’Z'))
   {
    letters++;
    flag = true;
   }
   else
   {
    flag = false;
   }

if(temp == ‘ ‘)
words ++;

}

  basic_string <char>::iterator str_Iter1;
  str_Iter1 = str.end();
  end = *(str_Iter1-1);
  if(end == ‘.’&& flag!= true)
   words++;
  if(flag == true && end!=’.')
   words++;
  if(words != 0)
   awlength = letters/words;

  if(awlength <= 3 && awlength >= 0)
   point = 250;
  else if(awlength == 4 || awlength == 5)
   point = 500;
  else if(awlength >= 6)
   point = 1000;
  return point;
}

};

这是完整的测试：

// HowEasy.cpp : 定义控制台应用程序的入口点。
//

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

class HowEasy
{
public:
int pointVal(string str)
{
  int point = 0;
  int awlength = 0;
  int words = 0;
  int letters = 0;
  char end = ”;
  bool flag = false;
  basic_string <char>::iterator str_Iter;
  for ( str_Iter = str.begin( ); str_Iter != str.end( ); str_Iter++ )
  {
   char temp = *str_Iter;
   if ((temp<= ‘z’&&temp>=’a')||(temp>=’A'&&temp<=’Z'))
   {
    letters++;
    flag = true;
   }
   else
   {
    flag = false;
   }

if(temp == ‘ ‘)
words ++;

}

  basic_string <char>::iterator str_Iter1;
  str_Iter1 = str.end();
  end = *(str_Iter1-1);
  if(end == ‘.’&& flag!= true)
   words++;
  if(flag == true && end!=’.')
   words++;
  if(words != 0)
   awlength = letters/words;

  if(awlength <= 3 && awlength >= 0)
   point = 250;
  else if(awlength == 4 || awlength == 5)
   point = 500;
  else if(awlength >= 6)
   point = 1000;
  return point;
}

};

int main()
{

HowEasy he;
cout<<”Please input the string:”<<endl;
string str;
getline(cin, str, ‘\n’);

int length = he.pointVal(str);
}

特别不好意思的是：C++的基本语法都忘记了，也很久没有写控制台的程序了，呵呵，都回忆了一下才想起来。真的很脸红。

Posted in Algorithm, TopCoder | No Comments »

HashTable vs DHT

十月 8th, 2007 by dolf

Hash table & DHT

先附上定义：In computer science, a hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person’s name), find the corresponding value (e.g. that person’s telephone number).

从上述定义来看，hash表完成的主要功能是查找。

举例说明：

假设某人爱好音乐，有N张CD。为了管理这些CD。此人设计了一个软件。该软件用HT实现查找，存储形式为数组array[N]。此人输入“SHE”，想得到的是和SHE相关的专辑放在什么位置，比如“第三层抽屉第一个CD包”

这里，关键字key是“SHE”，和关键字相关的value是“第三层抽屉第一个CD包”

假设使用的hash函数为Fhash。

（1）Fhash(SHE)=1011 ；hash函数将key变换成一个值，通常是一个数字串

（2）1011对应的数组位置为array[10]，；确定了数字串的存储位置，完成了地址的定位。

（3）程序将array[10]中的结果返回。查找结束。

在DHT里面，某个nodeQ(0010)节点（上面的应用程序）查找“SHE”，和SHE相关的专辑放在什么位置（哪个机器上nodeP(?)）？也就是查询返回的value应该是“nodeX有SHE”

假设nodeQ的路由表只有以下3项。

nodeF1 <-> (0011)

nodeF2 <-> (0111)

nodeF3 <-> (1010)

nodeF3的路由表由以下两项

nodeF4 <-> (1011)

nodeF5 <-> (1100)

nodeF4上面存的信息是“node1（192.168.10.1）和node2（192.168.44.8）存有SHE”

注意。NodeF4并不等价于node1或者node2。它可能是其中某一个节点，也可能不是。

（1）Fhash(SHE)=1011 ；hash函数将key变换成一个值，通常是一个数字串

（2）nodeQ并不知道1011对应哪个节点。它按照距离最近的原则，将查询分组requestSHE（1011）发送给nodeF3

（3）nodeF3收到requestSHE（1011）后，查找自己的路由表，发现nodeF4的ID为1011，将查询分组转发给nodeF4

（4）nodeF4收到requestSHE（1011）后，查找自己的缓冲区（或者硬盘…），将“node1（192.168.10.1）和node2（192.168.44.8）存有SHE”作为reply发送给nodeQ。

（5）nodeQ收到reply，得到想要查找的信息，查找完成。

对比两个查找过程。

HT: Fhash(SHE)->1011 ->a[10] ->“第三层抽屉第一个CD包”

DHT:Fhash(SHE)->1011->nodeF3 ->nodeF4 ->“node1（192.168.10.1）和node2（192.168.44.8）”

从上面的过程可以看到，Hash或者DHT提供的接口都是输入一个关键字，给出关键字对应的value，这个Value就是存储在DHT中的HT或者DHT用户（这个用户可能只是一个应用程序）所关心的信息。

那么，为什么节点nodeQ没有ID（1011）对应的节点IP地址呢？

从查找效率上来说，如果nodeQ具有所有在线的节点的IP地址和节点ID的映射，每次查找都只需要一步就能完成。不需要其他节点转发查询消息。效率最高。但是，这在动态变化的DHT中是不可能做到的。因为存储那么多节点ID和IP的映射需要存储开销，更重要的是，要维护路由表的正确性，需要大量的通信开销。这是任何节点和链路都无法承受的。所以，每个节点都只能维护一部分路由表。至于节点选择维护多大一部分（how much），选择维护哪一部分（which），不同的DHT协议有不同的见解，基本上是在DHT网络的通信开销和查询效率上折中。

那么，回到上次讨论的问题，路由表是不是hash表的一部分呢？

我自己的见解是，这个问题本身是不合适的。如果狭义的将hash表理解为就是静态的数组array[N]的地址，以及array[N]中所存的内容。那么路由表显然不是hash表。HT中Array[x]的地址是节点对应的ID，或者说，是Fhash(nodeX)所得到的值。array[x]中的下标x，对应的是节点的IP地址。而array[x]中保存的内容，是nodeX中保存的内容（或者是一部分内容）。

但是，我所理解的HT，是一种完整的算法，包括查询在内。而DHT，则是这种算法的分布式实现。

所以，路由表是完成DHT查找功能的重要的一部分。是hash算法的分布式实现的重要的一部分。

Posted in p2p | No Comments »

Hash函数学习

十月 8th, 2007 by dolf

Hash函数是一种映射关系，通过一种映射关系，将原本的字符串，数字或其他关键信息转换为一个索引值。
用数学关系式表示为：
index = function(key)

数序上有不同的映射关系，不同的key，有可能会获取相同的index，这个时候的index就是有重码，也就是collosion，这就导致了Hash函数的不唯一性，从而在查找index下的关键字时也是有冲突的。

目前一些常用的数学映射关系为：
   1、直接定址法，就是直接使用key作为index
   2、数字分析法，取key中的若干位数作为index，有较多冲突
   3、平法取中法，取key的平方，然后取中间几位作为index（index与key值密切相关），
   4、折叠法，将key从中间分割成几个部分，然后按照一定规则相加获取的结果为index。
   5、除留余数法，将key对某个数值m求余，获取的余数即为index，显然indxe<m，也就是如果key>m，必然会有n-m个冲突存在（n为key关键字的个数）。
   6、随机数法，将key值通过随机数求取index，即function（key）=random（key），伪随机数的均匀性较好，当关键字长度不相等时，用此法构造较为恰当。

解决冲突：
    其实并不是将冲突去掉，而是通过一种变通的方法，将冲突变得可以唯一查找，而不是有冲突就没有唯一的index位置了。
   解决方法有：
    一、开放定址法：
             index = （function（key）+di）mod m
               di：增长序列，m哈希表长，d的求取方法有下面集中。
      1、线性探测再散列，就是查找或插入时，如果发生冲突，就线性排列下去，下面还有冲突，继续排列下去，直到没有冲突时，查找结束或添加index。d=1，2，3，……，m-1
     2、二次探测再散列，d=1^2，-1^2，2^2，-2^2，……，±k^2（k<=m/2）
     3、伪随机探测再散列，d=random（key）
二、再Hash法
      即将index冲突的key关键字进行另一种Hash算法，得到key关键的index2索引值，从而来降低和避免冲突，当然要将冲突完全避免，则需要多个Hash算法隐含在其中。
三、链地址法
        当Index发生冲突时，将同一个index下冲突的key值都放在以index开头的链表中，这样index开头的链表中的key都可以比较方便的查找出来。
四、建立溢出表
         建立一个和key关键字一样多的index索引，当index发生冲突时，将所有发生冲突的key或index都放在溢出表中。

Hash表查找：

// ——-开放定址Hash表的存储结构————
int hashsize[]=…{997,…};  //Hash表容量递增表，一个合适的素数序列
typedef struct…{
   ElemType *elem;           //数据元素存储基址，动态分配数组
   int              count;          // 当前数据元素的个数
   int              sizeIndex;   //hashsize[sizeIndex]为当前容量
}HashTable;

//——–链接地址Hash表的存储结构—————
typedef struct childchain
{
ElemType data; // 数据值
struct childchain *next; // 下一个childchain值，NULL结束
}ChildChainHash

typedef struct mainchain{
    int index;   // 主链的索引值
    ChildChainHash *child; // 指向冲突的child子链，当没有冲突时，给予NULL值。
   struct mainchain *main; //
}MainChainHash;

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

采用链接构建Hash的思路，MainChainHash申请一个head指针和若干个变量，然后main指针依次指向下一个MainChainHash指针，而每一个child指针，指向ChildChainHash链中的值，这样一个Hash表就构造完成了。当主键key使用Hash一下获取的Index时，通过Index索引值知道Child链，从而构造了一个核实的Hash表。

// 采用开放式哈希表的存储结构

Status SearchHash(HashTable H, KeyType k, int &p, int &c)
…{
     // 开放地址哈希表H中查找关键字k的元素，若查找成功，以p指示待查数据，
   // 元素在表中位置，并返回SUCESS，否则，以p指示插入位置，并返回UNSUCESS，
   // c用以计冲突次数，其初值置零，供建表插入时参考
  p  = Hash(k);   // 求得hash地址表
  while( H.elem[p].key != NULLKEY &&   //该位置中填有记录
           !EQ( k,H.elem[p].key)                 // 并且关键字不相等
          collision( p, ++c) ;                  // 求得下一探索地址p
   if (EQ(K, H.elem[p].key ) )
          return SUCCESS;                 // 查找成功，p返回待查数据元素位置
   else
         return UNSUCESS;              // 查找不成功.( H.elem[p].key == NULLKEY )
                                                      // p返回的是插入的位置
}// SearchHash

Status InsertHash( HashTable &H, ElemType e)
…{
     // 查找不成功时，插入数据元素e到开放定址Hash表H中，并返回OK，
    // 若冲突次数过大，需重新构建Hash表
   c = 0;
   if( SearchHash( H,e.key,p,c ))
        return DUPLICATE;           // 表中已有与e有相同关键字的元素
  else if ( c <hashsize[H.sizeindex]/2 )  //冲突次数c未达到上限时，（c的阈值可调）
  …{
         H.elem[p] = e; ++H.count; return OK;    // 插入e
   }
   else
  …{
     RecreateHashTable(H);
    return UNSUCESS;    // 重建hash表
  }
}  // InsertHash
摘抄自严蔚敏的C数据结构中Hash章节。
Hash表最大的特点：
    不管n有多大，即表有多长，我们总可以选择一个合适的装填因子以便将来平均查找长度限定在一个范围之内。