I Will Never Stop~

2011年3月10日

之前已经写在CSDN上了，现在也转到这边一下。
问题描述：
设有N个人围坐一圈并按顺时针方向从1到N编号，从第S个人开始进行1到M报数，报数到第M个人时，此人出圈，再从他的下一个人重新开始1到M的报数，如此进行下去直到所有的人都出圈为止。现要打印出出圈次序。

输入：n 游戏总人数 s 报数的起始编号 m 报数的数值
输出：p 指向长度为n的数组，出圈次序保存在p指向的数组中
示例
   n=7 s=2 m=3 出圈次序为：4 7 3 1 6 2 5
   n=3 s=1 m=2 出圈次序为：2 1 3

1

#include <iostream>
2

#include <vector>
3

using namespace std;
4

/*
5

n=7 s=2 m=3 出圈次序为：4 7 3 1 6 2 5
6

n=3 s=1 m=2 出圈次序为：2 1 3
7

*/
8

void process(int n,int s,int m)
9

{
10

if(n<=0 || (s<1 || s>n) || m<=0)
11

{
12

cout<<"E8"<<endl;
13

return;
14

}
15

int MAX=n;
16

int start=s;
17

int step=m;
18

vector<int> men;
19

vector<int> outputList;
20

men.clear();
21

outputList.clear();
22

for (int i=0;i<MAX;i++)
23

men.push_back(i+1);
24

25

start=start-1;
26

27

int k=0;
28

while(!men.empty())
29

{
30

k=(start+step-1)%MAX;
31

outputList.push_back(men[k]);
32

men.erase(men.begin()+k);
33

MAX=men.size();
34

if (!MAX)
35

break;
36

start=k%MAX;
37

}
38

for (vector<int>::iterator it=outputList.begin();it!=outputList.end();it++)
39

cout<<*it<<" ";
40

cout<<endl;
41

}
42

int main()
43

{
44

int n,s,m;
45

while(cin>>n>>s>>m)
46

{
47

process(n,s,m);
48

}
49

return 0;
50

}

posted @ 2011-03-10 17:41 乔宁博阅读(737) | 评论 (0) | 编辑收藏

2010年10月11日

发一个二分查找的递归版本int B_search(int a[],int key,int size)

1

int B_search(int a[],int key,int size)
2

{
3

if(size<0)
4

return -1;
5

int mid=size/2;
6

if(a[mid]==key)
7

return mid;
8

else if(a[mid]>key)
9

return B_search(a,key,mid-1);
10

else if(a[mid]<key)
11

return B_search(a+mid+1,key,size-(mid+1))+mid+1;
12

}

posted @ 2010-10-11 23:52 乔宁博阅读(2055) | 评论 (6) | 编辑收藏

2010年10月1日

发一个归并排序的递归实现

1

#include <stdio.h>
2

#include <algorithm>
3

using namespace std;
4

#define MAX 1000
5

int buf[MAX];
6

void merge(int a[],int l,int m,int r)
7

{
8

int pa=l;
9

int pb=m+1;
10

int k=0;
11

12

while(pa<=m && pb<=r)
13

{
14

if(a[pa]<a[pb])
15

buf[k++]=a[pa++];
16

else
17

buf[k++]=a[pb++];
18

}
19

while(pa<=m)
20

buf[k++]=a[pa++];
21

while(pb<=r)
22

buf[k++]=a[pb++];
23

24

for(int i=0;i<k;i++)
25

a[l+i]=buf[i];
26

}
27

void mergeSort(int a[],int l,int h)
28

{
29

if(l<h)
30

{
31

int m=(l+h)/2;
32

mergeSort(a,l,m);
33

mergeSort(a,m+1,h);
34

merge(a,l,m,h);
35

}
36

}
37

void printIntArr(int n)
38

{
39

printf("%d ",n);
40

}
41

int main()
42

{
43

int a[10]={2,89,-1,8,0,7,13,0,11,3};
44

mergeSort(a,0,9);
45

//merge(a,0,4,9);
46

std::for_each(a,a+10,printIntArr);
47

return 0;
48

}

posted @ 2010-10-01 22:42 乔宁博阅读(1752) | 评论 (2) | 编辑收藏

2010年1月28日

创建win32透明窗体

本来是写在CSDN上的，现在转一下过来。
创建一个透明窗体，一种方法是设置windows下窗体的一个扩展窗口风格，在WINNT及以后，Windows开始支持用来创建透明窗体的一个API函数，先看一个效果图：

这一个GDI绘图的数字时钟的窗口。实现了窗口的半透明效果。实现方法如下：

1

#define _WIN32_WINNT 0x5000 //定义WINNT的宏
2

//

3

hwnd = CreateWindow(szAppName,TEXT("Noble Qiao~"),
4

WS_POPUP | WS_SYSMENU | WS_VISIBLE ,
5

::GetSystemMetrics(SM_CXSCREEN)/2,
6

::GetSystemMetrics(SM_CYSCREEN)/2,
7

160,45,
8

NULL,NULL,hInstance,NULL);
9

//

10

::SetWindowLong(hwnd,GWL_EXSTYLE,GetWindowLong(hwnd,GWL_EXSTYLE)|WS_EX_LAYERED);
11

SetLayeredWindowAttributes(hwnd,0,(255*70)/150,LWA_ALPHA);

SetLayeredWindowAttributes(hwnd,0,(255*70)/150,LWA_ALPHA);设置了窗体的属性，为透明效果，其中第二个参数为alpha值，即透明度。

另外，我在使用一个游戏引擎HGE做应用时，发现了关于这个API函数的一个问题，我把这个函数的调用放在初始化一些用于渲染场景的指针变量之前时，在 winxp下运行就会运行出错，而在 Vista 下完全正常。

我猜想在XP下，这个函数被调用后，直接调用wndproc，此时如果游戏资源（如纹理）没有被初始化，就会出错；而在Vista中没有这个问题，可能是Microsoft对这个API函数做了一定修改。

posted @ 2010-01-28 22:41 乔宁博阅读(7487) | 评论 (3) | 编辑收藏

2010年1月26日

vista & win7 下安装 VC6

         Visual Studio 6.0虽然是比较老(1998)的开发工具了，但是它体积比VS小，安装速度也快。
         在这里说的是 vc6 在 vista 和 win7 下的安装问题，因为之前在网上找的说的好像都比较乱。
          一开始只是听别人说，VC++6.0在vista下不兼容，用不了，自己先装了一下，设置成兼容模式&管理员身份运行，结果运行就崩溃，还以为真的不行，就没有去找传说中可以用的SP6版。
         网上搜索一般都是说SP6、管理员、兼容什么的，前几天需要再用VC6，所以就装了一下。在vista和win7下，安装时都会提示说不兼容什么的，直接把不再提示那个对话框勾一下，只管安装就是，vista和win7不一样的地方在于，vista下需要设为“管理员身份运行”，不能设置为“兼容模式”，win7下按刚才说的，安装完毕就可以运行了。

posted @ 2010-01-26 14:07 乔宁博阅读(4460) | 评论 (15) | 编辑收藏

2010年1月4日

poj1305 Fermat vs_ Pythagoras 一个简单的模拟题

          这个题目就是找在1~N之间互质的三个正整数x、y、z，并满足x^2+y^2=z^2，判断这样的数有多少对，以及跟1~N中与这些互质正整数无关的正整数的个数。
          其实比较关键的是对上面那个式子 x^2+y^2=z^2 进行变形，减少一个变量为
          (r^2-s^2)^2 + (2*r*s)^2 = (r^2+s^2)^2，
          这样只有两个变量存在，可以减少一轮循环。于是题目就变成了找这样的r和s，当r*r + s*s <= n时，
          z = r*r + s*s;
        y = max(r*r - s*s, 2*r*s);
         x = min(r*r - s*s, 2*r*s);
          此时，如果x、y、z互质，满足条件的正整数组计数就加1，同时把所有与这些数相关的数组位标记为1，

for (i = 1; i*z <= n; i++){
flag[i*x] = flag[i*y] = flag[i*z] = 1;
}

输出第二个结果的时候，即为输出标志数组中值为0的元素个数。

for (i = 1; i <= n; i++)
{
if (!flag[i])/*The second number is the number of positive integers <=N that are not part of any triple whose components are all <=N */
num++;
}

虽然在题目中说到N最大为1，000，000 ，但是poj测试数据大概在2000内。使用2001大小的标记数组就可以过。

posted @ 2010-01-04 11:04 乔宁博阅读(1511) | 评论 (0) | 编辑收藏

2009年12月23日

开篇

发现博客是一个学习、交流思想的一个很好的平台，以前都在看别人的博客，现在自己也开始写一下了。

posted @ 2009-12-23 15:14 乔宁博阅读(195) | 评论 (0) | 编辑收藏

常用链接

留言簿

随笔档案(7)

搜索

最新评论

阅读排行榜

评论排行榜