2009年6月18日

假定坐标系中,从点(0,0) 到 点 (m,n),只能上行或者右行,则可以到达的路径总数是多少?
每次只能移动一个单位

解法一:

组合数学的多重集合排列问题,设上行一个单位为 x,右行一个单位为y,则到达(m,n)点
的一条路径,对应于{m*x, n*y}的一个全排列。根据全排列公式,可有

    (m+n)!
__________ = C(m+n, m)
      m! n!


解法二:

将问题转化为DP问题,即 设 F(x,y)表示到达(x,y)的路径总数,则有
                  F(x,y) = F(x-1,y) + F(x, y-1);
其中有F(0,j) = 1, F(i, 0) = 1, i = 1...x;  j = 1.....y

代码如下:以 (9,9)点为列子
 1 # include <iostream>
 2 
 3 using namespace std;
 4 int F(int x, int y) {
 5     if ( x == 0 || y == 0)
 6         return 1;
 7     else
 8         return F(x-1,y) + F(x,y-1);
 9 }
10 int main() {
11     cout<<F(9,9)<<endl;
12 }
13 

posted @ 2009-06-18 17:37 Liu 阅读(254) | 评论 (0)编辑 收藏

给定一个序列
       a1, a2, a3, ...., aN
找出其中的递增的最长子序列


基本思想:DP的方法,对数字 ai 来说,假设前(1,2,....,i-1)个数字中的最长子序列长度为m,如果 ai 比这个子序列中的最大的一个数大,则 ai 加入到这个最长子序列,否则 goto a(i+1),代码如下

 1# include <iostream>
 2# include <vector>
 3# include <algorithm>
 4int main() {
 5
 6    int length = 8;
 7    int number[] = {1,-1,2,-3,4,-5,6,-7};
 8    
 9    std::vector<int> Lis(length);
10
11    for (int i = 0; i < length; i++{
12        Lis[i] = 1;
13        for (int j = 0; j < i; j++{
14            if (number[j] < number[i] && Lis[j] + 1 > Lis[i]) {
15                Lis[i] = Lis[j] + 1;
16            }

17        }

18    }

19    
20    std::cout<<*max_element(Lis.begin(), Lis.end())<<std::endl;
21
22    return 0;
23}

posted @ 2009-06-18 17:13 Liu 阅读(447) | 评论 (0)编辑 收藏

2009年6月16日

 1 # include <iostream>
 2 # include <string>
 3 # include <iterator>
 4 # include <vector>
 5 # include <algorithm>
 6 # include <sstream>
 7 
 8 int main () {
 9 
10     std::string line1 = "We were her pride of 10 she named us --";
11     std::string line2 = "Benjamin, Pheonix, the Prodigal";
12     std::string line3 = "and perspicacious pacific Suzanne";
13 
14     std::string sentence = line1 + ' ' + line2 + ' ' + line3;
15 
16 
17     std::string::size_type pos = 0;
18     std::string::size_type prepos = 0;
19     std::vector<std::string> words;
20 
21     /** Method 1
22     * filter the space using find_first_of
23     **/
24     //while ((pos = sentence.find_first_of(" ",pos))
25     //    != std::string::npos) {
26     //        words.push_back(sentence.substr(prepos,(pos-prepos)));
27     //        pos++;
28     //        prepos = pos;
29     //}
30 
31     /** Method 2
32     * filter the space using getline
33     **/
34     //std::stringstream ss(sentence);
35     //std::string temp;
36     //while(std::getline(ss,temp,' ')){
37     //    words.push_back(temp);
38     //}
39 
40 
41     /** Method 3
42     * filter the space using <<
43     **/
44     std::stringstream ss(sentence);
45     std::string temp;
46     while(ss>>temp){
47         words.push_back(temp);
48     }
49 
50 
51 /////////// filter the punctuations /////////////////////////////////
52     std::string punctuations(",--10");
53     std::vector<std::string>::iterator iter;
54     // filter the punctuations
55     for (iter = words.begin(); iter != words.end(); ++iter) {
56         pos = 0;
57         while((pos = (*iter).find_first_of(punctuations,pos))
58             != std::string::npos) {
59                 (*iter).erase(pos,1);
60         }
61         if((*iter).empty()) {
62             iter = words.erase(iter);
63             iter--;
64         }
65     }
66 
67     // output the filtered vector
68     std::ostream_iterator<std::string> output(std::cout,"\n");
69     std::copy(words.begin(),words.end(),output);
70 
71     return 0;
72 }

posted @ 2009-06-16 19:27 Liu 阅读(1152) | 评论 (0)编辑 收藏

istream::getline

public member function
istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );

Get line from stream

Extracts characters from the input sequence and stores them as a c-string into the array beginning at s.

Characters are extracted until either (n - 1) characters have been extracted or the delimiting character is found (which is delim if this parameter is specified, or '\n' otherwise). The extraction also stops if the end of file is reached in the input sequence or if an error occurs during the input operation.

If the delimiter is found, it is extracted and discarded, i.e. it is not stored and the next input operation will begin after it. If you don't want this character to be extracted, you can use member get instead.

The ending null character that signals the end of a c-string is automatically appended to s after the data extracted.

The number of characters read by this function can be obtained by calling to the member function gcount.

A global function with the same name exists in header <string>. This global function provides a similar behavior, but with standard C++ string objects instead of c-strings: see getline (string).

Parameters

s
A pointer to an array of characters where the string is stored as a c-string.
n
Maximum number of characters to store (including the terminating null character).
This is an integer value of type streamsize.
If the function stops reading because this size is reached, the failbit internal flag is set.
delim
The delimiting character. The operation of extracting succesive characters is stopped when this character is read. This parameter is optional, if not specified the function considers '\n' (a newline character) to be the delimiting character.

Return Value

The function returns *this.

Errors are signaled by modifying the internal state flags:

flagerror
eofbit The end of the source of characters is reached during its operations.
failbit No characters were extracted because the end was prematurely found.
This is also set if the function stops extracting because n-1 characters were extracted (n including the terminating null-character).
Notice that some eofbit cases will also set failbit.
badbit An error other than the above happened.

Additionaly, in any of these cases, if the appropriate flag has been set with member function ios::exceptions, an exception of type ios_base::failure is thrown.

Example

// istream getline
#include <iostream>
using namespace std;

int main () {
char name[256], title[256];

cout << "Enter your name: ";
cin.getline (name,256);

cout << "Enter your favourite movie: ";
cin.getline (title,256);

cout << name << "'s favourite movie is " << title;

return 0;
}

This example ilustrates how to get lines from the standard input stream ( cin ).

Basic template member declarations

( basic_istream<charT,traits> )

typedef charT char_type;
basic_istream& getline (char_type* s, streamsize n );
basic_istream& getline (char_type* s, streamsize n, char_type delim );

See also

istream::get Get unformatted data from stream (public member function)
istream::ignore Extract and discard characters (public member functions)
istream::gcount Get number of characters extracted by last unformatted input operation (public member function)

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////

     

getline为全局方法

getline function

istream& getline ( istream& is, string& str, char delim );
istream& getline ( istream& is, string& str );
<string>

Get line from stream

Extracts characters from is and stores them into str until a delimitation character is found.

The delimiter character is delim for the first function version, and '\n' (newline character) for the second. The extraction also stops if the end of file is reached in is or if some other error occurs during the input operation.

If the delimiter is found, it is extracted and discarded, i.e. it is not stored and the next input operation will begin after it.

Notice that unlike the c-string versions of istream::getline, these string versions are implemented as global functions instead of members of the stream class.

Parameters

is
istream object on which the extraction operation is performed.
str
string object where the extracted content is stored.
delim
The delimiting character. The operation of extracting succesive characters is stopped when this character is read.

Return Value

The same as parameter is.

Errors are signaled by modifying the internal state flags:

flagerror
eofbit The end of the source of characters is reached during its operations.
failbit No characters were extracted because the end was prematurely found.Notice that some eofbit cases will also set failbit.
badbit An error other than the above happened.

Additionaly, in any of these cases, if the appropriate flag has been set with is's member function ios::exceptions, an exception of type ios_base::failure is thrown.

Example


            
 1 // getline with strings
 2 #include <iostream>
 3 #include <string>
 4 using namespace std;
 5 
 6 int main () {
 7   string str;
 8   cout << "Please enter full name: ";
 9   getline (cin,str);
10   cout << "Thank you, " << str << ".\n";
11 }

This example ilustrates how to get lines from the standard input stream ( cin ).

Basic template member declarations

( basic_istream<charT,traits> )

template<class charT, class traits, class Allocator>
basic_istream<charT,traits>&
getline (basic_istream<charT,traits>& is,
basic_string<charT,traits,Allocator>& str,
charT delim );
template<class charT, class traits, class Allocator>
basic_istream<charT,traits>&
getline (basic_istream<charT,traits>& is,
basic_string<charT,traits,Allocator>& str );

See also

operator>> Extract string from istream (function)
istream::getline Get line from stream (public member function)

/////////////////////////////////////////////////////////////////////////////////////////////////////////////

posted @ 2009-06-16 19:18 Liu 阅读(2554) | 评论 (0)编辑 收藏

仅列出标题