在字符串s1中寻找字符串s2如果找到了就返回指针，否则返回NULL。
下面是这个函数的一个简单实现：
static const char* _strstr(const char* s1, const char* s2)
{
assert(s2 && s1);
const char* p=s1, *r=s2;
while(*p!=”)
{
while(*p++==*r++);
if(*r==”)
return p;
else
{
r=s2;
p=++s1;
}
}
return NULL;
}
11,半素数
题目定义了一种叫半素数的数：只要一个数能被分解成两个素数，那么这个数就是半素数。
Prime Number Definition
An integer greater than one is called a prime number if its only positive divisors (factors) are one and
itself. For instance, 2, 11, 67, 89 are prime numbers but 8, 20, 27 are not.
Semi-Prime Number Definition
An integer greater than one is called a semi-prime number if it can be decompounded to TWO prime numbers.
For example, 6 is a semi-prime number but 12 is not.
Your task is just to determinate whether a given number is a semi-prime number.
Input
There are several test cases in the input. Each case contains a single integer N (2 <= N <= 1,000,000)
Output
One line with a single integer for each case. If the number is a semi-prime number, then output "Yes",
第 5 页
数据结构面试大全
otherwise "No".
Sample Input
3
4
6
12
Sample Output
No
Yes
Yes
No
没什么好说的，解法很简单，解法如下：
#include
#include
using namespace std;
bool isprime(long test)
{
int i;
for(i=2;i<=sqrt((long double)test);i++)
{
if(test%i ==0)
return false;
}
return true;
}
bool isSemiPrime(long test)
{
int i;
for(i=2;i<=sqrt((long double)test);i++)
{
if(test%i ==0)
{
int temp = test/i;
return isprime(i) && isprime(temp);
}
}
return false;
}
int main()
{
long n;
while(cin>>n && n !=0)
{
if(isSemiPrime(n))
cout<<"Yes"<
else
cout<<"No"<
}
}
12,淘汰赛问题
题目：
Our school is planning to hold a new exciting computer programming contest. During each round of the
contest, the competitors will be paired, and compete head-to-head. The loser will be eliminated, and the
winner will advance to next round. It proceeds until there is only one competitor left, who is the
champion. In a certain round, if the number of the remaining competitors is not even, one of them will be
chosed randomly to advance to next round automatically, and then the others will be paired and fight as
usual. The contest committee want to know how many rounds is needed to produce to champion, then they
could prepare enough problems for the contest.
Input
The input consists of several test cases. Each case consists of a single line containing a integer N -
the number of the competitors in total. 1 <= N <= 2,147,483,647. An input with 0(zero) signals the end of
the input, which should not be processed.
Output
For each test case, output the number of rounds needed in the contest, on a single line.
Sample Input
8
16
15
0
Sample Output
3
4
4
题目比较简单，下面是我给的解法。其实就是计算一个数是2的几次方。
#include
第 6 页
数据结构面试大全
using namespace std;
long calculate(long test)
{
long ret = 0;
bool is2square = true;
while(test!=1)
{
if(test % 2)
is2square = false;
test /= 2;
ret++;
}
if(!is2square)
ret++;
return ret;
}
int main()
{
long n;
while(cin>>n && n !=0)
{
cout<
}
}
|