#include <graphics.h> #include <cmath> void control(int& x1,int& y1,int r1, int x2,int y2,int r2){ if(kbhit()){ char ch = getch(); if(ch == 'a') x1-=5; if(ch == 'd') x1+=5; if(ch == 'w') y1-=5; if(ch == 's') y1+=5; int deltax = abs(x1-x2),deltay = abs(y1-y2); int len = sqrt(deltax*deltax+deltay*deltay); if(len<r1+r2){ xyprintf(100,100,"碰撞了"); } } } int main(){ initgraph(640,480); int r1=20,r2=50; int x1=20,y1=20,x2=200,y2=200; while(is_run()){ circle(x1,y1,r1); circle(x2,y2,r2); control(x1,y1,r1,x2,y2,r2); delay_fps(60); cleardevice(); } closegraph(); return 0; }
#include <graphics.h> #include <cmath> void control(int& x1,int& y1,int w1,int h1,int x2,int y2,int w2,int h2){ if(kbhit()){ char ch = getch(); if(ch == 'a') x1-=5; if(ch == 'd') x1+=5; if(ch == 'w') y1-=5; if(ch == 's') y1+=5; if((abs((x1+w1/2)-(x2+w2/2))<(w1/2+w2/2)&&abs((y1+h1/2)-(y2+h2/2))<(h1/2+h2/2))){ xyprintf(100,100,"碰撞了"); } } } int main(){ initgraph(640,480); int w1 = 100, h1=40; int w2 = 100, h2=60; int x1=20,y1=20,x2=200,y2=200; while(is_run()){ rectangle(x1,y1,x1+w1,y1+h1); rectangle(x2,y2,x2+w2,y2+h2); control(x1,y1,w1,h1,x2,y2,w2,h2); delay_fps(60); cleardevice(); } return 0; }
#include <iostream> using namespace std; int arr[100]; void partition(int low, int hi, int& pivot){ int i, j; int temp; temp = arr[low]; j = low; for(i = low+1;i<=hi;i++) //从枢纽点后第一个数开始比较 if(arr[i]<temp){ //遇到比枢纽点小的 j++; //指针j向后移动 swap(arr[i], arr[j]);//并交换这两个元素 } //循环完毕 pivot = j; //快排递归需要的分割元素 swap(arr[low], arr[pivot]); //枢纽点就位,j就是猜测点应该呆的位置 } void quicksort(int low, int hi){ int pivot; if(hi > low){ partition(low, hi, pivot); quicksort(low, pivot-1);//排序枢纽点左侧 quicksort(pivot+1, hi); //排序枢纽点右侧 } } int main(int argc, char const *argv[]){ int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&arr[i]); quicksort(0, n-1); for (int i = 0; i < n; ++i) { cout <<arr[i]; } return 0; }
#include <cstdio> void merge( int h, int m, int* left, int* right, int *array){//合并两个数组 int i = 0, j = 0,k =0; while(i<h&&j<m){ if(left[i]<right[j]){ array[k] = left[k]; i++; } else { array[k] = right[k]; j++; } k++; } if(i==h){ for(int t=i;t<m;t++) array[k+t] = right[t]; } else { for(int t=j;t<h;t++) array[k+t] = left[t]; } } void mergesort(int n, int *array){//归并排序 if(n>1){ int h = n>>1, m = n - h; int left[h], right[m]; for(int i=0;i<h;i++) left[i] = array[i]; for(int i=0;i<m;i++) right[i] = array[h+i]; mergesort(h, left); mergesort(m, right); merge(h, m, left, right, array); } } int main(int argc, char const *argv[]) { int s[100]; int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&s[i]); mergesort(n, s); for (int i = 0; i < n; ++i) { /* code */ printf("%d ", s[i]); } return 0; }
#include <cstring> #include <cstdio> #define size 10 struct Event{ void (*events[size])() ={NULL};//回调函数数组 char str[size][100]; int top = 0; void callback(char *s, void (*func)()){ events[top] = func; strcpy(str[top],s); top++; } void handle(){ for(int i=0; i<top;i++){ events[i](); printf("%s\n", str[i]); } } }; void print(){ printf("hello\n" ); } int main(){ Event event; event.callback("test",print);//添加回调 event.handle(); //执行回调 return 0; }
#include <graphics.h> void compute(bool &r, bool& t, int& x, int& y, int rectx){ if(r){ x+=5; if(x==635) r=0; }else { x-=5; if(x==5) r=1; } if(t){ y+=5; if(x>=rectx&&x<=rectx+200&&y==465){ t=0; y-=5; } } else { y-=5; if(y<=0) t = 1; } if(y>465){ outtextxy(100,100,"你输了,按任意键开始"); if(kbhit()) y = 0; } } void moverect(int& x){ char ch; if(kbhit()){//判断输入 ch = getch();//把字符读入 if(ch =='a') x-=10; if(ch =='d') x+=10; } } int main(){ PIMAGE img; initgraph(640, 480); img = newimage(); getimage(img,"test.jfif");//加载图片到img画板,请替换成自己的图片 int x=100, y=100; bool r = 1; bool t = 1; int rectx = 400; //板子的x轴 setfillcolor(WHITE); while(is_run()){ xyprintf(100,100,"%f",getfps()); compute(r, t, x, y, rectx); //计算 fillellipse(x,y,10,10); moverect(rectx); rectangle(rectx,470,rectx+200,478); //画板子 delay_fps(60); cleardevice(); } delimage(img); //删除图像对象 closegraph(); return 0; }
题目:最长上升子序列 这是一道入门级动态规划题目,让我们尝试分析一波。 分析: 此处首先划分一下子问题,我们求解动态规划这类问题,首先可以划分一下子问题,再去找状态转移方程,最后写代码。 子问题:如果第n项能够与第n-1项的最长子序列构成一个更长子序列,那么第n项的最长子序列就是第n-1项的最长子序列加1,第一项的最长子序列是1。 状态转移方程: 设f[n]保存第n个数的最长序列,数组a保存数据 f[i] = max(f[i],f[i-1]+1) if a[i] > a[i-1] else f[i]=1 c++代码: #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define MAX 1000 int s[MAX]; int f[MAX]; int main(){ int n; cin >> n; memset(s, 0, sizeof(s)); memset(f,0,sizeof(f)); for(int i = 0; i < n; i++){ cin >> s[i]; f[i]=1; } for(int i = 0; i < n - 1; i++) for(int j = i + 1; j < n; j++) if(s[i] < s[j]) f[j] = max(f[j], f[i] + 1);//填充第n项的最长序列长度 cout <<*max_element(f,f+n)<< endl; //n个状态中的最大值 return 0; }
很简单,假如你住在32楼,现在你妈让你去楼下倒垃圾,你需要先下到31楼,再下到30楼再下到29楼。。。。。 到达1楼时你就倒了垃圾,但是还没回家给你妈报告,所以你还要回去,所以你需要一层一层返回到32楼。 为什么不能一次性解决问题呢?是因为没办法,你无法从32楼直接到达一楼,就算买了保险也不行。
数学归纳法是用于证明结论的正确性,而无法用于发现公式和定理。 证明:若nn是正整数,则1+2+....+n=n(n+1)21+2+....+n=\frac{n(n+1)}{2}。设P(n)P(n)是命题:前nn个数之和为n(n+1)2\frac{n(n+1)}{2}。基础步骤:当n=1n=1时,n(n+1)2\frac{n(n+1)}{2}成立。归纳步骤:假定任意正整数k,P(k)P(k)成立,则在此假定下,P(k+1)P(k+1)必定为真。 1+2+....+k=k(k+1)21+2+....+k=\frac{k(k+1)}{2},等式两边加上k+1k+1得:1+2+....+k+(k+1)=k(k+1)2+(k+1)1+2+....+k+(k+1)=\frac{k(k+1)}{2}+(k+1)右式等于:(k+1)(k+2)2=(k+1)((k+1)+1)2\frac{(k+1)(k+2)}{2}=\frac{(k+1)((k+1)+1)}{2}\thereforenn个数之和为n(n+1)2\frac{n(n+1)}{2}成立
P(n,r)P(n,r)代表元素总数为n的集合中取出r个元素进行排列 个数定理1: P(n,r)=n×(n1)×...×(nr+1)P(n,r)=n\times(n-1)\times...\times(n-r+1)也可写作 P(n,r)=nr+1nP(n,r) = \prod_{n-r+1}^{n}证明: 设 SS是具有 nn个元素的集合,我们取第一个元素时有nn种可能,取第二个元素时有n1n-1种可能,依次类推, 第 rr次有n(r+1)n-(r+1)种可能 ( r<nr<n)。我们要获取P(n,r)P(n,r)可用全排列即 n!n!除去多余部分排列(即 0nr\prod_0^{n-r} )。并约定0!=10!=1,所以证得: P(n,r)=n!(nr)!=nr+1nP(n,r)=\frac{n!}{(n-r)!} =\prod_{n-r+1}^{n}此证明过于简洁,仅作参考。前缀知识包括计数乘法定理。