当前位置:文档之家› 算法竞赛入门经典1-3章习题答案

算法竞赛入门经典1-3章习题答案

算法竞赛入门经典1-3章习题答案
算法竞赛入门经典1-3章习题答案

第一章习题1-1

#include

int main()

{

int a,b,c;

double d;

scanf("%d%d%d",&a,&b,&c);

d=(double)(a+b+c);

printf("%.3lf\n",d/3.0);

return 0;

}

习题1-2

#include

int main()

{

int f;

double c;

scanf("%d",&f);

c=5.0*(f-32)/9;

printf("%.3lf\n",c);

return 0;

}

习题1-3

#include

int main()

{

int n;

scanf("%d",&n);

printf("%d\n",(n*(1+n))/2);

return 0;

}

习题1-4

#include

#include

#define pi 4.0*atan(1.0)

int main()

{

int n;

scanf("%d",&n);

printf("%lf\n",sin((pi*n)/180));

printf("%lf\n",cos((pi*n)/180));

return 0;

}

习题1-5

#include

#include

int main()

{

double x1,y1,x2,y2,a;

scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);

a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

printf("%lf\n",a);

return 0;

}

习题1-6

#include

int main()

{

int n;

scanf("%d",&n);

if(n%2==0)

{

printf("yes\n");

}

else

{

printf("no\n");

}

return 0;

}

习题1-7

#include

int main()

{

int n;

double a;

scanf("%d",&n);

a=n*95.0;

if(a<300)

{

printf("%.2lf\n",a);

}

else

{

printf("%.2lf\n",a*0.85);

}

return 0;

}

习题1-8

#include

#include

int main()

{

double n;

scanf("%lf",&n);

printf("%.2lf",fabs(n));

return 0;

}

习题1-9

#include

int main()

{

int a,b,c;

scanf("%d%d%d",&a,&b,&c);

if((a*a+b*b==c*c)||(a*a+c*c==b*b)||(b*b+c*c==a*a)) {

printf("yes\n");

}

else

{

printf("no\n");

}

return 0;

}

习题1-10

#include

int main()

{

int n;

scanf("%d",&n);

if(n%4==0)

{

if(n%100!=0)

{

printf("yes\n");

}

else

{

if(n%400==0)

{

printf("yes\n");

}

else

{

printf("no\n");

}

}

}

else

{

printf("no\n");

}

return 0;

}

第二章习题2-1

#include

int main()

{

int n,count=0;

scanf("%d",&n);

while(n>0)

{

count++;

n=n/10;

}

printf("%d\n",count);

return 0;

}

习题2-2

#include

int main()

{

int a,b,c;

for(int i=100;i<=999;i++)

{

a=i%10;

b=i/10%10;

c=i/100;

if(i==a*a*a+b*b*b+c*c*c)

{

printf("%d\n",i);

}

}

return 0;

}

习题2-3

#include

int main()

{

int i,a,b,c;

scanf("%d%d%d",&a,&b,&c);

for(i=10;i<=100;i++)

{

if(i%3==a&&i%5==b&&i%7==c)

{

printf("%d\n",i);break;

}

if (i==100)printf("no answer\n");

}

return 0;

}

习题2-4

#include

int main()

{

int i,j,k,n;

scanf("%d",&n);

for(i=n;i>0;i--)

{

for(k=0;k

{

printf("");

}

for(j=0;j<2*i-1;j++)

{

printf("#");

}

printf("\n");

}

return 0;

}

习题2-5

文件题,南邮竞赛基本不涉及。。。习题2-6

#include

int main()

{

int i,n;

double sum=1.0;

scanf("%d",&n);

for(i=2;i<=n;i++)

{

sum+=(1.0/i);

}

printf("%.3lf\n",sum);

return 0;

}

习题2-7

#include

#include

int main()

{

double sum = 0, a = 1.0;

for(int i = 1; (1.0/i) > (1e-6); ++i)

{

sum += a/(2*i-1);

a *= -1;

}

printf("%.8lf %.8lf\n", sum, 4*sum); return 0;

习题2-8

#include

int main()

{

int i,n,m,temp;

double sum=0;

scanf("%d%d",&n,&m);

if(n>m)

{

temp=n;

n=m;

m=temp;

}

for(i=n;i<=m;i++)

{

sum=sum+(1.0/i/i);

}

printf("%.5lf\n",sum);

return 0;

}

本题陷阱在于1/(n)^2 + ...,用1/(n*n)会溢出,改为1/n/n就好。

习题2-9

printf的特殊用法:对于m.n的格式可以用如下方法表示

char ch[20];

printf("%*.*s\n",m,n,ch);

前边的*定义的是总的宽度,后边的定义的是输出的个数。分别对应外面的参数m和n 。这种方法的好处是可以在语句之外对参数m和n赋值,从而控制输出格式。

#include

int main()

{

int a,b,c;

scanf("%d%d%d",&a,&b,&c);

printf("%.*lf\n",c,(double)a/b);

return 0;

}

习题2-10

解法1:#include

int main()

{

int a,b,c,d,e,f,g,h,i;

for(a=1;a<=9;a++)

{

for(b=1;b<=9;b++)

{

for(c=1;c<=9;c++)

{

for(d=1;d<=9;d++)

{

for(e=1;e<=9;e++)

{

for(f=1;f<=9;f++)

{

for(g=1;g<=9;g++)

{

for(h=1;h<=9;h++)

{

for(i=1;i<=9;i++)

{

if((2*(a*100+b*10+c)==1*(d*100+e*10+f))&&(3*(a*100+b*10+c)==1*(g*100+h*10+i))& &(a!=b)&&(a!=c)&&(a!=d)&&(a!=e)&&(a!=f)&&(a!=g)&&(a!=h)&&(a!=i)&&(b!=c)&&(b!=d)&&(b !=e)&&(b!=f)&&(b!=g)&&(b!=h)&&(b!=i)&&(c!=d)&&(c!=e)&&(c!=f)&&(c!=g)&&(c!=h)&&(c!=i )&&(d!=e)&&(d!=f)&&(d!=g)&&(d!=h)&&(d!=i)&&(e!=f)&&(e!=g)&&(e!=h)&&(e!=i)&&(f!=g)&& (f!=h)&&(f!=i)&&(g!=h)&&(g!=i)&&(h!=i))

{

printf("%d,%d,%d\n",a*100+b*10+c,d*100+e*10+f,g*100+h*10+i);

}

}

}

}

}

}

}

}

}

}

return 0;

}

解法二:

#include

int main()

{

int x, y, z, a[10] = {0};

for(x = 100; x < 333; x++)

{

y = 2*x;

z = 3*x;

//令a[出现的数字] = 1

a[x/100] = a[x/10%10] = a[x%10] = 1; a[y/100] = a[y/10%10] = a[y%10] = 1; a[z/100] = a[z/10%10] = a[z%10] = 1; int i, s = 0;

for(i = 1; i < 10; i++)

s += a[i];

if(s == 9)

printf("%d\t%d\t%d\n", x, y, z); for(i = 1; i < 10; i++) //重新赋值为0 a[i] = 0;

}

return 0;

}

第三章

习题3-1 分数统计

输入一些学生的分数,哪个分数出现的次数最多?如果有多个并列,从小到大输出。

任务1:分数均为不超过100的非负整数

任务2:分数均为不超过100的非负实数,但最多保留两位小数

解法1:

#include

usingnamespace std;

#define Max 10001 //定义数组最大长度为10001,可以在成绩为100时不超出边界

int main()

{

int score[Max];

double s[Max];

int n,time,count=0;

double a;int c;double b;

for(int i=0;i

score[i]=0;

cout<<"人数为:";

cin>>n;

for(int j=0;j

{

cin>>a;

c=a*100;

score[c]++;

}

time=score[0];

for(int j=1;j

{

if(score[j]>time)

{

time=score[j];

b=j;

cout<<"出现最多次数的分数是:"<

}

} /*b中存放的数据即为出现次数最多分数中第一次出现的分数,time中存放的数据为该分数出现最大次数*/

for(int j=0;j

if(score[j]==time&&j!=b)

s[count++]=j;

for(int i=0;i

cout<

return 0;

} //该程序虽然简单,但运算量极大,不适合数据及时性要求较高的系统

解法2:

#include

#include

int main()

{

int i,a[101],n,max;

memset(a,sizeof(a),0); //将数组a全置为0

while(scanf("%d",&n)==1)

{

a[n]++;

} //通过对输入的n的记录,统计出输入次数,并存于数组a中

/*scanf函数返回的是成功输入的变量数目,当输入完毕后先按enter键,再按ctrl+z键,最后再按enter键,即可结束输入*/

max=a[0];

for(i=1;i<101;i++)

{

if(a[i]>=max)

{

max=a[i];

}

}

for(i=0;i<101;i++)

{

if(a[i]==max)

{

printf("%d ",i);

}

}

printf("\n");

return 0;

}

注:解法二仅适用于输入成绩为整数的情况

解法三:

#include

#include

#define MAXN 5000

int s[MAXN],m[MAXN][2];

int main()

{

double x;

int i=0,j=0,temp=0,length,min,max=0,last; while(scanf("%lf",&x) == 1)

{

temp=x*1000;

temp=temp%10;

if (temp>=5) s[i++]=x*100+1;

else

s[i++]=x*100;

}

printf("\n");

length = i-1;

for(i=0;i<=length;i++)

{

min=s[i];

for (j=length;j>=i;j--)

{

if (min>s[j])

{

min=s[j];

s[j]=s[i];

s[i]=min;

}

}

} //将数组中的值按从小到大排序

for (i=0;i<=length;i++) printf("%d ",s[i]); printf("\n");

j=0;

for(i=0;i<=length;i++)

{

last=i-1;

if ((i>0)&&(s[last]==s[i]))

{

m[j][1]++;

if (max

}

else

{

if (i!=0) j++;

m[j][0]=s[i];

m[j][1]=1;

}

}//将数组中的元素置于二维数组中,并记录相同元素个数,j中存放的是不同元素的个数

for(i=0;i<=length;i++)

{

if (m[i][1]==max)

printf("%.2lf\n",m[i][0]/100.0) ;

}

return 0;

}

习题3-2 单词的长度

输入若干个单词,输出它们的平均长度。单词只包含大写字母和小写字母,用一个或多个空格隔开

解法1:

#include

#include //isalpha函数调用

char s[1000];

int main()

{

char ch;

int i,j,m=0,sumlong=0,count=0;

while(1)

{

scanf("%c",&ch);

if(ch=='\n'||ch==EOF)

{

break;

}

else

{

s[m++]=ch;

}

}

for(i=m-1;i>0;i--)

{

if(s[i]==' '&&s[i-1]==' ')

{

for(j=i-1;j

{

s[j]=s[j+1];

}

m--;

}

}

/*若程序输入两个以上的空格,则删除多余的空格,只保留一个空格,并更改数组元素个数*/ for(i=0;i

{

if(isalpha(s[i]))

{

sumlong++;

}

else if(s[i]==' ')

{

count++;

}

}

printf("%.2lf\n",(double)((sumlong+count+1)/(count+1)));

return 0;

}

解法二:

#include

#include

#include

#define A 100000+10 /*假定用户输入字符的最多个数*/

int main()

{

char a[A]; /*存储用户输入的字符数据*/

int y,

tot=0, /*用户输入的字母的总数*/

word=0, /*单词的个数*/

i;

gets(a);

i=strlen(a);

tot=i;

for (y=0;y

if (isspace(a[y])) tot=tot-1;

if (

(y==0 && !isspace(a[y])) /*如果数组下标为a0的元素不为空格,则算找到了一个单词。(数组最开始的地方,要特别处理。)*/

||

(y>0 && isspace(a[y-1]) && !isspace(a[y])) /*如果数组中某个下标比0大的元素不为空格,且该元素的前一个元素是空格,则算是找到了一个单词*/

) word=word+1;

}

if (word==0) printf("没有输入任何单词”);

else printf("单词的平均长度是%f",(tot*1.0)/word);

return 0;

}

习题3-3 乘积的末3位

输入若干个整数(可以是正数、负数或者零),输出它们的乘积的末三位。这些整数中会混

入一些由大写字母组成的字符串,你的程序应当忽略它们。提示:试试看,在执行scanf

(“%d”)时输入一个字符串会怎样?

#include

#include

#include

#define MAXN 5000

char a[MAXN];

int b[MAXN];

int main()

{

int i,j=0,chuli=0,fuhao=1,kongge=0;

long plus=1;

fgets(a,sizeof(a),stdin);

for (i=0;i<=strlen(a);i++)

{

printf("%d %d %c\n",i,a[i],a[i]);

chuli=0;

if (((a[i]==45)||(a[i]==32)||(a[i]==0))||((a[i]>=48)&&(a[i]<=57)))

chuli=1;

if (chuli==1)

{

if (a[i]==45)

{

fuhao=(-1)*fuhao;

}

else

{

if((a[i]==32)||(a[i]==0))

{

if (kongge==0)

{

kongge=1;

fuhao=1;

j++;

}

}

else

{

kongge=0;

b[j]=(a[i]-48)*fuhao+b[j]*10;

printf("b[%d]=%d\n",j,b[j]);

}

}

}

if(a[i]==0) printf("EOF");

}

for (i=0;i<=j-1;i++)

{

plus*=b[i];

printf("b[%d]=%d plus=%d\n",i,b[i],plus);

}

printf("%03d",abs(plus%1000));

return 0;

}

习题3-4 计算器

编写程序,读入一行恰好包含一个加号、减号或乘号的表达式,输出它的值。这个运算符保证是二元运算符,且两个数均为不超过100的非负整数。运算数和运算符可以紧挨着,也可以用一个或多个空格、TAB隔开。行首末尾均可以有空格。提示:选择合适的输入方法可以将问题简化。

样例输入:1+1

样例输出:2

样例输入:2- 5

样例输出:-3

样例输入:0 *1982

样例输出:0

#include

#define MAXN 5000

int main()

{

int a,b,c;

char f;

scanf("%d",&a);

scanf("%c",&f);

while((f!='+')&&(f!='-')&&(f!='*')) scanf("%c",&f); scanf("%d",&b);

if (f=='+') c=a+b;

else

if(f=='-') c=a-b;

else

c=a*b;

printf("%d",c);

return 0;

}

习题3-5 选择

输入一个n*n的字符矩阵,把它左转90度后输出。

解法一:

#include

char a[1000][1000];

int main()

{

int i,j,n;

scanf("%d",&n);

scanf("");

char temp;

for(i=0;i

{

for(j=0;j

{

scanf("%c",&a[i][j]);

}

}

for(i=0;i

{

for(j=i;j

{

temp=a[i][j];

a[i][j]=a[j][i];

a[j][i]=temp;

}

}

for(i=n-1;i>=0;i--)

{

for(j=0;j

{

printf("%c ",a[i][j]);

}

printf("\n");

}

return 0;

}

解法二:

#include

#define MAXN 5000

char a[MAXN][MAXN];

int main()

{

int i=0,j=0,k,n;

while(scanf("%c",&a[i][j])==1)

{

if (a[i][j]!='\n') j++;

else {i++;j=0;}

printf("i=%d j=%d\n",i,j); }

n=i;

for (j=n-1;j>=0;j--)

{ for (i=0;i<=n-1;i++)

printf("%c",a[i][j]); printf("\n");

}

}

习题3-6 进制转换1

输入基数b(2<=b<=10)和正整数n(十进制),输出n的b进制表示。#include

int main()

{

int a[10],b,i=0,j=0,n;

scanf("%d %d", &b, &n);

while(n>0)

{

a[i]=n%b;

n=n/b;

printf("%d %d \n",n,a[i]);

i++;

}

for(j=i-1;j>=0;j--)

printf("%d",a[j]);

return 0;

}

习题3-7 进制转换2

输入基数b(2<=b<=10)和正整数n(b进制),输出n的十进制表示。

#include

int ndjc(int n,int m)

{

int i,a=1;

for(i=0;i

{

a*=m;

}

return a;

}

int main()

{

int i,b,n,p[100],m=0,a=0;

scanf("%d %d",&b,&n);

while(n>0)

{

p[m++]=n%10;

n=n/10;

}

m--;

for(i=m;i>=0;i--)

{

a+=p[i]*ndjc(i,b);

蓝书刘汝佳算法竞赛入门经典勘误

#《算法竞赛入门经典》勘误 关于勘误?下面的勘误很多来自于热心读者,再次向他们表示衷心的感谢!我并不清楚这些错误实际是在哪个版本中改正过来的,所以麻烦大家都看一下。 有发现新错误的欢迎大家在留言中指出,谢谢! 一些一般性的问题?运算符?已经被废弃,请用min、max代替(代码仓库中的代码已更新,g++ 4.6.2下编译通过) 重大错误?p24. 最后一行,“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而min=INF”。 (感谢imxivid) p43. 最后,判断s[i..j]是否为回文串的方法也不难写出:int ok = 1; for(k = i; i<=j; i++)应该为for(k = i; k<=j; k++) (感谢imxivid) p45. 第七行和第九行i-j+1应为i+j+1。修改后: 1. { 2. for (j = 0; i - j >= 0 && i + j < m; j++) 3. { 4. if (s[i - j] != s[i + j]) break; 5. if (j*2+1 > max) { max = j*2+1; x = p[i - j]; y = p[i + j];} 6. } 7. for (j = 0; i - j >= 0 && i + j + 1 < m; j++) 8. { 9. if (s[i - j] != s[i + j + 1]) break; 10. if (j*2+2 > max) 11. {max = j*2+2; x = p[i - j]; y = p[i + j + 1]; } 12. } 13. }p53. 例题4-1. 组合数. 输入非负整数n和m,这里的n和m写反了。应是“输入非负整数m和n”。 p54. 举例中的m和n也写反了(真是个悲剧),且C(20,1)=20。 p71. 《周期串》代码的第8行,j++应为i++。 p72. 代码的第7行,“return”改为“break”以和其他地方一致。 p81. k为奇数和偶数的时候,分子和分母的顺序是不一样的。正确代码为: #include int main() { int n; while(scanf("%d", &n) == 1) { int k = 1, s = 0; for(;;) { s += k; if(s >= n) { if(k % 2 == 1) printf("%d/%d\n", s-n+1, k-s+n); else printf("%d/%d\n", k-s+n, s-n+1); break; } k++; } } return 0; }以及: #include #include int main() { int n; while(scanf("%d", &n) == 1) { int k = (int)floor((sqrt(8.0*n+1)-1)/2 - 1e-9)+1; int s = k*(k+1)/2; if(k % 2 == 1) printf("%d/%d\n", s-n+1, k-s+n); else printf("%d/%d\n", k-s+n, s-n+1); } return 0; }上述代码已经更新到代码仓库中。 p83. 应为am * an = am+n。 (感谢zr95.vip) p85. 两张插图下面的文字“顺时针”、“逆时针”反了。 (感谢zr95.vip) p107. dfs函数有误,应为: void dfs(int x, int y) { if(!mat[x][y] || vis[x][y]) return; // 曾经访问过这个格子,或者当前格子是白色vis[x][y] = 1; // 标记(x,y)已访问过dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1); dfs(x ,y-1); dfs(x ,y+1); dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); // 递归访问周围的八个格子}(感谢zhongying822@https://www.doczj.com/doc/9d561367.html,) p124. 图7-5最右边的有两个结点(3,1,*,*),应该只有一个。下面一段第一行的“它只有18

统计学经典习题集参考答案

1.要了解某班50名学生的性别构成情况,则总体是()。 A.每一个学生 B.每一个学生的性别 C.全体学生 D.全体学生的性别 2.要了解全国的人口情况,总体单位是()。 A.每一个人 B.每一户 C.每个省的人口 D.全国总人口 3.某班四名学生金融考试成绩分别为70分、80分、86分和90分,这四个数字是()。 A.变量值 B.标志 C.指标值 D.指标 4.工业企业的职工人数、职工工资是()。 A.离散变量 B.前者是离散变量,后者是连续变量 C.连续变量 D.前者是连续变量,后者是离散变量 5.统计学与统计工作的关系是()。 A.理论与应用的关系 B.工作与结果的关系 C.理论与实践的关系 D.工作与经验的关系 6.某地区为了掌握该地区水泥生产的质量情况,拟对占该地区水泥总产量的90%的五个大型水泥厂的生产情况进行调查,这种调查方式是()。 A.典型调查 B.重点调查 C.抽样调查 D.普查 7.某地进行国有商业企业经营情况调查,则调查对象是()。 A.该地所有商业企业 B.该地所有国有商业企业 C.该地每一家商业企业 D.该地每一家国有商业企业 8.对企业先按经济类型分组,再按企业规模分组,属于()。 A.简单分组 B.平行分组 C.复合分组 D.再分组 9.某变量数列,其末组为开口组,下限为600,又知其相邻组的组中值为550,则末组的组中值是()。 A.100 B.500 C.650 D.700 10.统计表的宾词是用来说明总体特征的()。 A.统计指标 B.总体单位 C.标志 D.统计对象 11.下面属于时期指标的是()。 A.商品销售额 B.商场数量 C.商品价格 D.营业员人数 12.用水平法检查长期计划完成程度,应规定()。 A.计划期初应达到的水平 B.计划期末应达到的水平 C.计划期中应达到的水平 D.整个计划期应达到的水平 13.第五次人口普查结果,我国每10万人中具有大学程度的为3611人。该数字资料为()。 A.绝对数 B.结构相对数 C.比较相对数 D.强度相对数 14.某商场计划11月份销售利润比10月份提高2%,实际提高了3%,则销售利润计划完成程度为()。 A.100.98% B.95.10% C.99.00% D.105.10% 15.平均数反映了()。 A.总体分布的集中趋势 B.总体分布的离中趋势 C.总体中各单位分布的集中趋势 D.总体变动的趋势 16.中位数和众数是一种()。 A.常见值 B.代表值 C.实际值 D.典型值 17.计算发展速度的分母是()。 A.计划期水平 B.固定期水平 C.报告期水平 D.基期水平 18.由一个10项的时间序列可以计算的环比发展速度有()。 A.8个 B.9个 C.10个 D.11个

贪心算法经典例题

贪心算法经典例题 发布日期:2009-1-8 浏览次数:1180 本资料需要注册并登录后才能下载! ·用户名密码验证码找回密码·您还未注册?请注册 您的账户余额为元,余额已不足,请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。 从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌(NOIP2002tg) [问题描述] 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为: ①9 ②8 ③17 ④ 6 移动3次可达到目的: 从③取 4 张牌放到④(9 8 13 10) -> 从③取 3 张牌放到②(9 11 10 10)-> 从②取 1 张牌放到①(10 10 10 10)。 [输入]:键盘输入文件名。 文件格式:N(N 堆纸牌,1 <= N <= 100) A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输出]:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in: 4 9 8 17 6 屏慕显示:3 算法分析:设a[i]为第i堆纸牌的张数(0<=i<=n),v为均分后每堆纸牌的张数,s为最小移到次数。 我们用贪心法,按照从左到右的顺序移动纸牌。如第i堆(0

数值计算方法试题及答案

【 数值计算方法试题一 一、 填空题(每空1分,共17分) 1、如果用二分法求方程043=-+x x 在区间]2,1[内的根精确到三位小数,需对分( )次。 2、迭代格式)2(2 1-+=+k k k x x x α局部收敛的充分条件是α取值在( )。 3、已知?????≤≤+-+-+-≤≤=31)1()1()1(211 0)(2 33x c x b x a x x x x S 是三次样条函数, 则 a =( ), b =( ), c =( )。 4、)(,),(),(10x l x l x l n 是以整数点n x x x ,,,10 为节点的Lagrange 插值基函数,则 ∑== n k k x l 0)(( ), ∑== n k k j k x l x 0 )(( ),当2≥n 时 = ++∑=)()3(20 4x l x x k k n k k ( )。 ; 5、设1326)(2 47+++=x x x x f 和节点,,2,1,0,2/ ==k k x k 则=],,,[10n x x x f 和=?07 f 。 6、5个节点的牛顿-柯特斯求积公式的代数精度为 ,5个节点的求积公式最高代数精度为 。 7、{}∞ =0)(k k x ?是区间]1,0[上权函数x x =)(ρ的最高项系数为1的正交多项式族,其中1)(0=x ?,则?= 1 4)(dx x x ? 。 8、给定方程组?? ?=+-=-2211 21b x ax b ax x ,a 为实数,当a 满足 ,且20<<ω时,SOR 迭代法收敛。 9、解初值问题 00 (,)()y f x y y x y '=?? =?的改进欧拉法 ??? ??++=+=++++)],(),([2),(] 0[111] 0[1n n n n n n n n n n y x f y x f h y y y x hf y y 是 阶方法。

统计与概率经典例题(含答案和解析).docx

统计与概率经典例题(含答案及解析) 1.(本题8 分)为了解学区九年级学生对数学知识的掌握情况,在一次数学检测中, 从学区2000 名九年级考生中随机抽取部分学生的数学成绩进行调查,并将调查结果绘 制成如下图表: ⑴表中 a 和 b 所表示的数分别为:a= .,b=.; ⑵请在图中补全频数分布直方图; 2000 名九年级考生数学⑶如果把成绩在70 分以上(含70 分)定为合格,那么该学区 成绩为合格的学生约有多少名? 2.为鼓励创业,市政府制定了小型企业的优惠政策,许多小型企业应运而生,某镇统 计了该镇 1﹣ 5 月新注册小型企业的数量,并将结果绘制成如下两种不完整的统计图: ( 1)某镇今年1﹣5 月新注册小型企业一共有家.请将折线统计图补充完整; ( 2)该镇今年 3 月新注册的小型企业中,只有 2 家是餐饮企业,现从 3 月新注册的小型企业中随机抽取 2 家企业了解其经营状况,请用列表或画树状图的方法求出所抽取的 2家企业恰好都是餐饮企业的概率. 3.( 12 分)一个不透明的口袋装有若干个红、黄、蓝、绿四种颜色的小球,小球除颜 色外完全相同,为估计该口袋中四种颜色的小球数量,每次从口袋中随机摸出一球记下颜 色并放回,重复多次试验,汇总实验结果绘制如图不完整的条形统计图和扇形统计图.

根据以上信息解答下列问题: (1)求实验总次数,并补全条形统计图; (2)扇形统计图中,摸到黄色小球次数所在扇形的圆心角度数为多少度? (3)已知该口袋中有 10 个红球,请你根据实验结果估计口袋中绿球的数量. 4.(本题 10 分)某校为了解2014 年八年级学生课外书籍借阅情况,从中随机抽取了 40名学生课外书籍借阅情况,将统计结果列出如下的表格,并绘制成如图所示的扇形 统计图,其中科普类册数占这40 名学生借阅总册数的40%. 类别科普类教辅类文艺类其他册数(本)12880m48 ( 1)求表格中字母m的值及扇形统计图中“教辅类”所对应的圆心角 a 的度数; (2)该校 2014 年八年级有 500 名学生,请你估计该年级学生共借阅教辅类书籍约多少本? 5.( 10 分)将如图所示的版面数字分别是1, 2,3, 4 的四张扑克牌背面朝上,洗匀后放在桌面上(“ A”看做是“ 1”)。 ( 1)从中随机抽出一张牌,牌面数字是偶数的概率是;(3分) ( 2)从中随机抽出两张牌,两张牌面数字的和是 5 的概率是;(3分)(3)先从中随机抽出一张牌,将牌面数字作为十位上的数字,然后将该牌放回并重新洗 匀,再随机抽取一张,将牌面数字作为个位上的数字,请用画树形图的方法求组成的

算法习题

算法设计与分析试卷 一、填空题(20分,每空2分) 1、算法的性质包括输入、输出、确定性、有限性。 2、动态规划算法的基本思想就将待求问题分解成若干个子问题、先求解子问题,然后 从这些子问题的解得到原问题的解。 3、设计动态规划算法的4个步骤: (1)找出最优解的性质,并刻画其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值得到的信息,构造最优解。 4、流水作业调度问题的johnson算法: (1)令N1={i|ai=bj}; (2)将N1中作业依ai的ai的非减序排序;将N2中作业依bi的非增序排序。 5、对于流水作业高度问题,必存在一个最优调度π,使得作业π(i)和π(i+1)满足Johnson不等式min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}。 6、最优二叉搜索树即是最小平均查找长度的二叉搜索树。 二、综合题(50分) 1、当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时,最大子段和为∑ak(2<=k<=4)=20(5分) 2、由流水作业调度问题的最优子结构性质可知,T(N,0)=min{ai+T(N-{i},bi)}(1=sum){ sum=thissum; besti=i; bestj=j;} } return sum; } 4、设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree? (15分) Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w) { for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]= 0;} for(int r=0;r

最新算法竞赛入门经典各章(第二版)前4章课后习题答案电子教案

第一章习题1-1 #include int main() { int a,b,c; double d; scanf("%d%d%d",&a,&b,&c); d=(double)(a+b+c); printf("%.3lf\n",d/3.0); return 0; } 习题1-2 #include int main() { int f; double c; scanf("%d",&f); c=5*(f-32)/9; printf("%.3lf\n",c); return 0;

习题1-3 #include int main() { int n; scanf("%d",&n); printf("%d\n",(n*(1+n))/2); return 0; } 习题1-4 #include #include #define pi 4.0*atan(1.0) int main() { int n; scanf("%d",&n); printf("%lf\n",sin((pi*n)/180)); printf("%lf\n",cos((pi*n)/180)); return 0;

习题1-5 #include int main() { double x1,y1,x2,y2,a; scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); printf("%lf\n",a); return 0; } 习题1-6 #include int main() { int n; scanf("%d",&n); if(n%2==0) { printf("YES\n"); }

贪心算法概论

贪心算法概论 贪心算法一般来说是解决“最优问题”,具有编程简单、运行效率高、空间 复杂度低等特点。是信息学竞赛中的一个有为武器,受到广大同学们的青睐。本 讲就贪心算法的特点作些概念上的总结。 一、贪心算法与简单枚举和动态规划的运行方式比较 贪心算法一般是求“最优解”这类问题的。最优解问题可描述为:有n个输入,它的解是由这n 个输入的某个子集组成,并且这个子集必须满足事先给定的条 件。这个条件称为约束条件。而把满足约束条件的子集称为该问题的可行解。这 些可行解可能有多个。为了衡量可行解的优劣,事先给了一个关于可行解的函数,称为目标函数。目标函数最大(或最小)的可行解,称为最优解。 a)求“最优解”最原始的方法为搜索枚举方案法(一般为回溯法)。 除了极简单的问题,一般用深度优先搜索或宽度优先搜索。通常优化方法为利用约束条件进行可行性判断剪枝;或利用目标函数下界(或上界),根据当前最 优解进行分枝定界。 b)其次现今竞赛中用的比较普遍的动态规划(需要满足阶段无后效性原则)。 动态规划主要是利用最最优子问题的确定性,从后向前(即从小规模向大规模)得到当前最优策略,从而避免了重复的搜索。 举例说明:求多段图的最短路径。

在图(1)中,我们省略了各线段的长度。 如果用回溯法,搜索树大致如下: 显然,上面的搜索有大量重复性工作。比如节点8、9、10到11的最短路分别被调用了9次,从节点5、6、7到节点11也分别搜索了3次。 如果先算出节点8、9、10到11的最短路,由于它与前面的点无关,因此最优值确定下来,再用它们求定节点5、6、7 到节点11 的最短路径。同理,再用节 点5、6、7 的最优值,来求节点2、3、4 优值。最后从节点2、3、4 推出1 到 11的最优值。显然复杂度大为降低。 当然,如果本题把简单搜索改为搜索+记忆化的方法,则就是得能动态规划的原理,本质上就是动态规划,只是实现的方法不同与传统的表格操作法。搜索+记忆化算法有其特有的特点,以后再讨论。 c)贪心算法则不同,它不是建立在枚举方案的基础上的。它从前向后,根据当前情况,“贪心地”决定出下一步,从而一步一步直接走下去,最终得到解。 假如上面的例子中,我们定下这样的贪心策略:节点号k%3= =1。则有图3:

C语言经典算法100例题目

看懂一个程序,分三步:1、流程;2、每个语句的功能;3、试数; 小程序:1、尝试编程去解决他;2、看答案;3、修改程序,不同的输出结果; 4、照答案去敲; 5、调试错误; 6、不看答案,自己把答案敲出来; 7、实在不会就背会。。。。。周而复始,反复的敲。。。。。 【程序1】 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? ============================================================== 【程序2】 题目:企业发放的奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高 于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可可提 成7.5%;20万到40万之间时,高于20万元的部分,可提成5%;40万到60万之间时高于 40万元的部分,可提成3%;60万到100万之间时,高于60万元的部分,可提成1.5%,高于 100万元时,超过100万元的部分按1%提成,从键盘输入当月利润I,求应发放奖金总数? ============================================================== 【程序3】 题目:一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?============================================================== 【程序4】 题目:输入某年某月某日,判断这一天是这一年的第几天? ============================================================== 【程序5】 题目:输入三个整数x,y,z,请把这三个数由小到大输出。 ============================================================== 【程序6】 题目:用*号输出字母C的图案。 ============================================================== 【程序7】 题目:输出特殊图案,请在c环境中运行,看一看,Very Beautiful! ============================================================== 【程序8】 题目:输出9*9口诀。 ============================================================== 【程序9】 题目:要求输出国际象棋棋盘。 ============================================================== 【程序10】 题目:打印楼梯,同时在楼梯上方打印两个笑脸。 -------------------------------------------------------------------------------- 【程序11】 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月 后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? ==============================================================

大师兄教你如何过华为机试

大师兄教你如何过华为机试 宝典1—内功心法 大华为这个大数据时代土豪金海量式的招聘又要开始了!!! 近期听说大华为的校招机试马上就要开始了,由于华为软件岗位的招聘只有技术面跟机试是与技术有关的内容,所以机试的地位非常重要。对于机试,除了长期积累的软件基本功以外,还有很多可以短期训练的东西,类似于考试之前的突击,可以迅速提高机试成绩,就像在我西电大杨老师考前最后一堂课一定要去,那个重点就是考点阿。 这篇机试葵花宝典的内容是针对华为软件类上机准备的,如果你认真看了本宝典,如果你是真正通过自己能力考上西电的话,想不过都难。同样想拿高级题的同学,请移步 https://www.doczj.com/doc/9d561367.html,/land/或者https://www.doczj.com/doc/9d561367.html,,刷上200道题,机试不想拿满分都难。 对于机试,首先应该调整好自己的心态,不要觉得写程序很难,机试题很难,也不要去考虑,万一机试考到自己不会的内容怎么办,要相信,机试题永远是考察每个人的基础,基础是不会考的很偏的,会有人恰好做过某个题而做出来那个题,但不会有人恰好没做过一个题而做不出来那个题。 机试之前,应该做的准备有: 1、买一本《算法竞赛入门经典》,这本书不同于普通的算法或者编程语言的书籍,这 本书既讲语言,又讲算法,由浅入深,讲的很好,能看完前几章并且把例题都做 会,想通过机试就很简单了 2、调整好心态,时刻告诉自己,哪些小错误是自己以前经常犯的,最好用笔记本记录 下来,写每道题前再看一遍,如果遇到代码调不出来了,先想想自己是否犯过以 前那些错误。还有就是,看了题目以后,先仔细想清楚细节,在纸上写清楚自己 需要用到的变量,以及代码的基本框架,不要急于动手去写代码 3、不要惧怕任何一道看起来很难的题目,有不会的就去问身边会的人,让别人给自己 讲清楚 4、心中默念10遍C++跟C除了多了两个加号其实没有区别,会C就能上手C++ 5、大量的练习是必要且有效的 6、看完这篇宝典,预过机试、必练此功。 在这里推荐一个帖子,是机试归来的学长写的,写的很不错,里面的例题在后面的攻略

统计学经典题库与答案

2. 数据筛选的主要目的是( A 、发现数据的错误 C 、找出所需要的某类数据 3. 为了调查某校学生的购书费用支出, B 、对数据进行排序 D 纠正数据中的错误 将全校学生的名单按拼音顺序排列后,每 ) A H 0:二=0.15;二-0.15 B H o :二二 0.15;二=0.15 C H 0: 一 - 0.15;二:: 0.15 D H 0:二乞 0.15;二 0.15 9. 若甲单位的平均数比乙单位的平均数小, 大,则( )。 A 、甲单位的平均数代表性比较大 C 甲单位的平均数代表性比较小 10. 某组的向上累计次数表明( A 、 大于该组上限的次数是多少 B 、 小于该组下限的次数是多少 但甲单位的标准差比乙单位的标准差 B 、两单位的平均数一样大 D 、无法判断 1.当正态总体方差未知时,在大样本条件下,估计总体均值使用的分布是 ( A )。 z 分布 B 、t 分布 F 分布 D 、 2 分布 A 、比平均数高出2个标准差 C 等于2倍的平均数 D 5.峰态通常是与标准正态分布相比较而言的。 则峰态系数的值( )。 B 比平均数低2个标准差 等于2倍的标准差 如果一组数据服从标准正态分布, A =3 C 、v 3 6. 若相关系数r=0,则表明两个变量之间( A 、相关程度很低 C 不存在任何关系 7. 如果所有变量值的频数都减少为原来的 1/3, 均数( )。 A 、不变 B C 减少为原来的1/3 D > 3, =0 )。 不存在线性相关关系 存在非线性相关关系 而变量值仍然不变,那么算术平 扩大到原来的3倍 不能预测其变化 8. 某贫困地区所估计营养不良的人高达 15%然而有人认为这个比例实际上还要 高,要检验该说法是否正确,则假设形式为( )。 隔50名学生抽取一名进行调查,这种调查方式是( A 、简单随机抽样 B 、分层抽样 C 、系统抽样 D 、整群抽样 4. 如果一组数据标准分数是(-2 ),表明该数据( )。

算法分析与设计期末模拟试题

安徽大学2010-2011学年第1学期《算法分析与设计》 期末试题 押宝 (内部交流,非考试试题,学生自发交流创作,版权归作者testfudan@https://www.doczj.com/doc/9d561367.html, 所有) 一、选择题(单选)(10*2’=20’) 1. 选择正确的组合对于 2112n +=( ) ①2()o n ② 2()O n ③2()n θ ④2()n Ω ⑤ 2()n ω A. ①③④ B. ②③④ C.③④⑤ D. ①⑤ 2. ①21()()n i i O n O n ==∑ ②2()()n O n O n = ③(log )()O n O n ? ④ 2.99993 ()n O n = ⑤2/lo g ()n n n ω=其中正确的有( ) A .5组 B.4组 C.3组 D.没有正确的 3. 2/102n n +=( ) A. 2()O n B.(2)n O C.2(2)n n O + D.2 ()o n 4. 211/n += ( )(我认为是比较不错的一道题,考试可能会出现相同的方法,用极限定义来做,最后一节课老师也讲过类似的方法) A. ()O n B.()o n C.()n Ω D.(1)O 5. 310lo g n = ( ) A.(log )O n n B. (log )O n C. 3()O n D. lo g ()n O n 6. 认真完成课后习题P5面的算法分析题1-6,里面也有我不会做的,可是有谁愿意讨论? 如果能够把以上的题目都能做对,应该就是掌握了。给自己一个奖励吧!答案(如有问题,联系我吧):1-5:BBBDB 6.做出来对对答案吧。 二、填空题 1.()2(/2)T n T n n =+????的一个渐进上界为 (答案:(log )O n n ,用迭代法) 2.()(/3)(2/3)()T n T n T n O n =++的一个渐进上界为 (答案:(log )O n n ,用递归树求解,不会的赶快看) 3.()9(/3)T n T n n =+的一个渐进紧致界为 (答案:2 ()n θ,采用迭代法或者采用主方法,不会的赶快看)

ACM经典算法及配套练习题

POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学:

(完整)信息学奥赛(NOIP)必看经典书目汇总,推荐文档

信息学奥赛(NOIP)必看经典书目汇总! 小编整理汇总了一下大神们极力推荐的复习资料!(欢迎大家查漏补缺) 基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》(推荐指数:4颗星) 曹文,吴涛编著,知识点大杂烩,部分内容由学生撰写,但是对初赛知识点的覆盖还是做得相当不错的。语言是pascal的。 2、谭浩强老先生写的《C语言程序设计(第三版)》(推荐指数:5颗星) 针对零基础学C语言的筒子,这本书是必推的。 3、《骗分导论》(推荐指数:5颗星) 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程(一)》(推荐指数:5颗星) 传说中的黄书。吴文虎,王建德著,系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著,传说中的红书。 6、《算法竞赛入门经典》(推荐指数:5颗星) 刘汝佳著,算法必看经典。 7、《算法竞赛入门经典:训练指南》(推荐指数:5颗星) 刘汝佳著,《算法竞赛入门经典》的重要补充 提高篇 1、《算法导论》(推荐指数:5颗星) 这是OI学习的必备教材。

2、《算法艺术与信息学竞赛》(推荐指数:5颗星) 刘汝佳著,传说中的黑书。 3、《学习指导》(推荐指数:5颗星) 刘汝佳著,《算法艺术与信息学竞赛》的辅导书。(PS:仅可在网上搜到,格式为PDF)。 4、《奥赛经典》(推荐指数:5颗星) 有难度,但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》(推荐指数:5颗星) 历年真题,这是绝对不能遗失的存在。必须要做! 三、各种在线题库 1、题库方面首推USACO(美国的赛题),usaco写完了一等基本上就没有问题,如果悟性好的话甚至能在NOI取得不错的成绩. 2、除此之外Vijos也是一个不错的题库,有很多中文题. 3、国内广受NOIP级别选手喜欢的国内OJ(Tyvj、CodeVs、洛谷、RQNOJ) 4、BJOZ拥有上千道省选级别及以上的题目资源,但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高,命题人大多为现役集训队选手。

高二81统计随机抽样直方图茎叶图知识点经典例题及练习题带答案

环球雅思教育学科教师讲义 讲义编号: ______________ 副校长/组长签字:签字日期: 【考纲说明】 1、理解随机抽样的必要性和重要性,了解分布、样本数据标准差的意义和作用,理解用样本估计总体的思想。 2、会画频率分布直方图、频率折线图、茎叶图,会用随机抽样的基本方法和样本估计总体的思想解决一些简单的实际问题 【趣味链接】 U2合唱团在17分钟内得赶到演唱会场,途中必需跨过一座桥,四个人从桥的同一端出发,你得帮助他们到达另一端,天色很暗,而他们只有一只手电筒。一次同时最多可以有两人一起过桥,而过桥的时候必须持有手电筒,所以就得有人把手电筒带来带去,来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同,若两人同行则以较慢者的速度为准。BONO需花1分钟过桥,EDGE需花2分钟过桥,ADAM需花5分钟过桥,LARRY需花10分钟过桥,他们要如何在17分钟内过桥呢? 【知识梳理】 一、抽样方法与总体分布的估计 1、随机抽样 (1)总体:在统计学中, 把研究对象的全体叫做总体,把每个研究对象叫做个体,把总体中个体的总数叫做总体容量.总体与个体之间的关系类似于集合与元素的关系. (2)样本:从总体中随机抽取一部分个体叫做总体的一个样本,样本中个体的数目称为样本的容量,样本和总体之间

的关系类似于子集和集合之间的关系. (3)简单随机抽样:一般地,从元素个数为N 的总体中不放回地抽取容量为的样本,如果每一次抽取时总体中的各个个体被抽到的可能性是相同的,那么这种抽样方法叫简单随机抽样,这样抽取的样本,叫做简单随机样本. 常用的方法有抽签法和随机数表法. (4)系统抽样:当总体中的个体比较多时,将总体分成均衡的若干部分,然后按照预先制定的规则,从每一部分中抽取一个个体,得到所需要的样本,这样的抽样方法称为系统抽样,也称作等距抽样. (5)分层抽样:当总体由有明显差别的几部分组成时,为了使抽取的样本更好地反映总体的情况,可将总体中各个个体按某种特征分成若干个互不重叠的几部分,每一部分叫做层,在各层中按层在总体中所占比例进行简单随机抽样或系统抽样,这种抽样方法叫做分层抽样. 2、频率分布直方图与茎叶图 (1)频率分布:样本中所有数据(或数据组)的频数和样本容量的比就是该数据的频率,所有数据(或数据组)的频率的分布变化规律叫做频率分布,可以用频率分布表、频率分布折线图、茎叶图、频率分布直方图来表示. (2)频率折线图:如果将频率分布直方图中各相邻的矩形的上底边的中点顺次连接起,就得到一条折线,称这条折线为本组数据的频率折线图。 (3)总体密度曲线:随着样本容量的增加,作图时所分的组数增加,组距减小,相应的频率折线图会越来越接近于一条光华曲线,即总体密度曲线。 (4)制作茎叶图的方法是:将所有两位数的十位数字作为“茎”,个位数字作为“叶”,茎相同者共用一个茎,茎按从小到大的顺序从上向下列出,共茎的叶一般按从大到小(或从小到大)的顺序同行列出. 茎叶图对于分布在0~99的容量较小的数据比较合适,此时,茎叶图比直方图更详尽地表示原始数据的信息. 在茎叶图中,茎也可以放两位,后面位数多可以四舍五入后再制图. 3、样本的数字特征 (1)众数:出现次数最多的数叫做众数. (2)中位数:如果将一组数据按大小顺序依次排列,把处在最中间位置的一个数据或中间两个数据的平均是叫做这组数据的中位数. (3)平均数与加权平均数:如果有n 个数,,,,n x x x x ??321那么12n x x x x n ++???+= 叫做这n 个数的平均数. 如果在n 个数中,1x 出现次1f 次, 2x 出现次2f 次,……,k x 出现次2f 次,(这里),n f f f k =+??++21那么 11221 ()k k x x f x f x f n =++???+叫做这n 个数的加权平均数,其中k f f f ??,,21叫做权. (4)标准差与方差:设一组数据123n x x x x ?,,,,的平均数为x ,则

贪心算法的应用

从贪心算法的定义可以看出,贪心法并不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌(NOIP2002tg) [问题描述] 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为: ①9 ②8 ③17 ④6 移动3次可达到目的: 从③取 4 张牌放到④(9 8 13 10) -> 从③取 3 张牌放到②(9 11 10 10)-> 从②取 1 张牌放到①(10 10 10 10)。 [输入]:键盘输入文件名。 文件格式:N(N 堆纸牌,1 <= N <= 100) A1 A2 … An (N 堆纸牌,每堆纸牌初始数,l<= Ai <=10000) [输出]:输出至屏幕。格式为:所有堆均达到相等时的最少移动次数。 [输入输出样例] : 4 9 8 17 6 屏慕显示:3 算法分析:设a[i]为第i堆纸牌的张数(0<=i<=n),v为均分后每堆纸牌的张数,s为最小移到次数。 我们用贪心法,按照从左到右的顺序移动纸牌。如第i堆(0v,则将a[i]-v张纸牌从第I堆移动到第I+1堆; (2)若a[i]

BIG NUMBER 算法竞赛入门经典 刘汝佳

424-Integer Inquiry One of the first users of BIT's new supercomputer was Chip Diller.He extended his exploration of powers of3to go from0 to333and he explored taking various sums of those numbers. ``This supercomputer is great,''remarked Chip.``I only wish Timothy were here to see these results.''(Chip moved to a new apartment,once one became available on the third floor of the Lemon Sky apartments on Third Street.) Input The input will consist of at most100lines of text,each of which contains a single VeryLongInteger.Each VeryLongInteger will be100or fewer characters in length,and will only contain digits(no VeryLongInteger will be negative). The final input line will contain a single zero on a line by itself. Output Your program should output the sum of the VeryLongIntegers given in the input. Sample Input 123456789012345678901234567890 123456789012345678901234567890 123456789012345678901234567890 Sample Output 370370367037037036703703703670 10106–Product The Problem The problem is to multiply two integers X,Y.(0<=X,Y<10250) The Input The input will consist of a set of pairs of lines.Each line in pair contains one multiplyer. The Output For each input pair of lines the output line should consist one integer the product. Sample Input 12 12 2 222222222222222222222222 Sample Output 144 444444444444444444444444 465–Overflow Write a program that reads an expression consisting of two non-negative integer and an operator.Determine if either integer or the result of the expression is too large to be represented as a``normal''signed integer(type integer if you are working Pascal,type int if you are working in C). Input An unspecified number of lines.Each line will contain an integer,one of the two operators+or*,and another integer. Output For each line of input,print the input followed by0-3lines containing as many of these three messages as are appropriate: ``first number too big'',``second number too big'',``result too big''. Sample Input 300+3 9999999999999999999999+11 Sample Output 300+3 9999999999999999999999+11 first number too big

相关主题
文本预览
相关文档 最新文档