博文
[置顶] 丢硬币：正面朝上的最大连续序列--passed！(2009-08-27 20:54:00)
摘要：
#include<iostream>
#include<ctime>
#include<string>
using namespace std;
int main()
{
//create sequence:
static int m=1;
int digits[1000],max[600],i=0;
srand((unsigned)time(0)); //如果用srand(time(0))会有警告
for(i=0;i<1000;i++)
digits[i]=rand()%2;
for(i=0;i<1000;i++)
cout<<digits[i];
cout<<endl<<endl;
// deal with sequence:
//memset(max,1,600*sizeof(max));
for(i=0;i<600;i++)
{
max[i]=1;
}
for(i=0;i<1000;i++) //注意max[m]的初始化
{
if(digits[i]==1)
{
max[m]++;
}
else
{
m++;
}
}
cout<<"m: "<<m<<endl;
int maximum=max[0];
for(i=0;i<m;i++)......
[置顶] 用C++模拟龟兔赛跑(2009-07-31 20:36:00)
摘要：// Chapter 5 of C++ How to Program
// tortoiseandhare.cpp
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
#include <ctime>
#include <iomanip>
using std::setw;
const int RACE_END = 70;
/* Write prototype for moveTortoise here */
void moveTortoise(int &);
/* Write prototype for moveHare here */
void moveHare(int &);
/* Write prototype for printCurrentPositions here */
void printCurrentPositions(int &,int &);
int main()
{
int tortoise = 1, hare = 1, timer = 0;
srand( time( 0 ) );
cout<<"A program to show the match between the tortoise and the hare!"<<endl<<endl;
cout << "ON YOUR MARK, GET SET\nBANG !!!!"
<<endl
<< "\nAND THEY’RE O......
opencv编程入门3 --图像处理(2009-11-23 13:41:00)
摘要：
图像处理
分配与释放图像空间
分配图像空间: IplImage* cvCreateImage(CvSize size, int depth, int channels);
size: cvSize(width,height);
depth: IPL_DEPTH_8U, IPL_DEPTH_8S, IPL_DEPTH_16U,
IPL_DEPTH_16S, IPL_DEPTH_32S, IPL_DEPTH_32F, IPL_DEPTH_64F
channels: 1, 2, 3 or 4.
注意数据为交叉存取.彩色图像的数据编排为b0 g0 r0 b1 g1 r1 ...
举例: // 分配一个单通道字节图像
IplImage* img1=cvCreateImage(cvSize(640,480),IPL_DEPTH_8U,1);
// 分配一个三通道浮点图像
IplImage* img2=cvCreateImage(cvSize(640,480),IPL_DEPTH_32F,3);
释放图像空间: IplImage* img=cvCreateImage(cvSize(640,480),IPL_DEPTH_8U,1);
cvReleaseImage(&img);
复制图像: IplImage* img1=cvCreateImage(cvSize(640,480),IPL_DEPTH_8U,1);
IplImage* img2;
img2=cvCloneImage(img1);
设定/获取兴趣区域: void cvSetImageROI(IplImage* image, CvRect rect);
void &n......
求数组的子数组的的元素之和的最大值3(2009-09-17 19:19:00)
摘要：
下面我们来分析一下最大子段和的子结构，令b[j]表示从a[0]~a[j]的最大子段和，b[j]的当前值只有两种情况，(1) 最大子段一直连续到a[j] (2) 以a[j]为起点的子段，不知有没有读者注意到还有一种情况，那就是最大字段没有包含a[j]，如果没有包含a[j]的话，那么在算b[j]之前的时候我们已经算出来了，注意我们只是算到位置为j的地方，所以最大子断在a[j]后面的情况我们可以暂时不考虑。
由此我们得出b[j]的状态转移方程为：b[j]=max{b[j-1]+a[j],a[j]},
所求的最大子断和为max{b[j],0<=j<n}。进一步我们可以将b[]数组用一个变量代替。
得出的算法如下：
int maxSubArray(int n,int a[])
{
int b=0,sum=-10000000;
for(int i=0;i<n;i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;
}
return sum;
&......
求数组的子数组的的元素之和的最大值2(2009-09-17 16:36:00)
摘要：
第二种方法－带记忆的递推法：
cumarr[0]=a[0]
for i=1 to n //首先生成一些部分和
{
cumarr[i]=cumarr[i-1]+a[i];
}
maxsofar=0
for i=0 to n
{
for j=i to n //下面通过已有的和递推
{
sum=cumarr[j]-cumarr[i-1]
if(sum>maxsofar)
maxsofar=sum
}
}
......
求数组的子数组的的元素之和的最大值(2009-09-17 15:22:00)
摘要：
给定一个长度为n的一维数组a，请找出此数组的一个子数组,使得此子数组的和sum＝a[i]+a[i+1]+……+a[j]最大
//算法一：
#include<iostream>
using namespace std;
int main()
{
int a[10]={0};
int max=0,i=0,j,k,temp=0;
for(i=0;i<10;i++)
{
cin>>a[i];
}
max=a[0];
for(i=0;i<10;i++)
{
for(j=i;j<10;j++)
{
for(k=i;k<=j;k++)
temp+=a[k];
max=(max>temp? max:temp);
temp=0;
}
}
cout<<max<<endl;
return 0;
}......
PKU 1050 动态规划-解决最大子矩阵问题【转】(2009-09-17 14:47:00)
摘要：
最大子矩阵问题：
问题描述：(具体见http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1050)
给定一个n*n(0<n<=100)的矩阵，请找到此矩阵的一个子矩阵，并且此子矩阵的各个元素的和最大，输出这个最大的值。
Example：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
其中左上角的子矩阵：
9 2
-4 1
-1 8
此子矩阵的值为9+2+(-4)+1+(-1)+8=15。
我们首先想到的方法就是穷举一个矩阵的所有子矩阵，然而一个n*n的矩阵的子矩阵的个数当n比较大时时一个很大的数字 O(n^2*n^2)，显然此方法不可行。
怎么使得问题的复杂度降低呢？对了，相信大家应该知道了，用动态规划。对于此题，怎么使用动态规划呢？
让我们先来看另外的一个问题(最大子段和问题)：
给定一个长度为n的一维数组a，请找出此数组的一个子数组,使得此子数组的和sum＝a[i]+a[i+1]+……+a[j]最大，其中i>=0,i<n,j>=i,j<n，例如
31 -41 59 26 -53 58 97 -93 -23 84
子矩阵59+26-53+58+97=187为所求的最大子数组。
第一种方法－直接穷举法:
maxsofar=0;
for i = 0 to n
{
for j = i to n
{
sum=0;
&......
PKU 1018 看不明白题目耶······(2009-09-17 13:50:00)
摘要：
郁闷。连题目都看不明白···········
哪位朋友可以给我讲讲题目意思吗？
谢啦！......
PKU ACM 1319--Pipe Fitters(2009-09-16 23:50:00)
摘要：
#include<iostream>
#include<cmath>
using namespace std;
int grid(float width,float height)// use string ???
{
int h=(int)height;
int w=(int)width;
return h*w;
}
int skew1(float width,float height)
{
int m1=(int)(width-0.5),n1=(int)((2*(height-1)/sqrt(3.0))+1);
int m2=(int)(height-0.5),n2=(int)((2*(width-1)/sqrt(3.0))+1);
return m1*n1>m2*n2? m1*n1:m2*n2;
}
int skew2(float width,float height)
{
int m1=(int)width,n1=(int)((2*(height-1)/sqrt(3.0))+1);
int m2=(int)height,n2=(int)((2*(width-1)/sqrt(3.0))+1);
int N1,N2;
if(n1%2==0)
N1=int(m1*n1-n1/2);
else
N1=int(m1*n1+n1/2-0.5);
if(n2%2==0)
N2=int(m2*n2-n2/2);
else
N2=int(m2*n2+n2/2-0.5);
return N1>N2? N1:N2;
}
int main()
{
float w,h;
int max=0;
while(cin>>w>......
PKU 北大ACM详解 转自百度百科(2009-09-16 21:57:00)
摘要：PKU 北大ACM详解 转自百度百科
2009-04-09 04:27 P.M.
北大ACM题分类
主流算法：
1.搜索 //回溯
2.DP（动态规划）
3.贪心
4.图论 //Dijkstra、最小生成树、网络流
5.数论 //解模线性方程
6.计算几何 //凸壳、同等安置矩形的并的面积与周长
7.组合数学 //Polya定理
8.模拟
9.数据结构 //并查集、堆
10.博弈论
1、 排序
1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379,
1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 2231 2371（简单排序） 2388（顺序统计算法） 2418（二叉排序树）
2、 搜索、回溯、遍历
1022 1111d 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078
,2083,2303,2310,2329
简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426,
不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349,
推荐：1011, 1......