haihongyuan.com
海量文库 文档专家
当前位置:首页 >> 教育学 >>

(HDUACM201403版_02)简单数学题_7805229_图文

(HDUACM201403版_02)简单数学题_7805229_图文

ACM程序设计
杭州电子科技大学 刘春英 acm@hdu.edu.cn

课前的一些问题:
一、关于课件

二、关于教材
三、关于选课 四、关于作业(helloworld)

2016/5/7

2

今天,



了吗?

2016/5/7

3

每周一星(1):

pathway

2016/5/7

4

第二讲

基础数学题

2016/5/7

5

“依然”从简单题说起:
? ? ? ? ? ?
?

SUM(n) = 1 + 2 + 3 + ... + n You may assume the result will be in the range of 32-bit signed integer. Sample input: 10 Sample output: 55
http://acm.hdu.edu.cn/showproblem.php?pid=1001
2016/5/7 6

很常见的一种写法:
?

?
? ?

?
? ? ? ?

#include<stdio.h> int main() { int n, i, sum=0; scanf("%d",&n); for(i=1;i<=n;i++) sum=sum+i; printf("%d\n",sum); return 0; }
2016/5/7 7

其它方法?
? ?

SUM(n) = 1 + 2 + 3 + ... + n = n * (n+1) / 2

? ?

什么风险? 如何处理?

2016/5/7

8

OJ评测原理
STD-I 10 STD-I 50000 STD-O 55 6 STD-O 6 ? TMP-O 55 TMP-O ??

2016/5/7

9

有什么问题呢?
享受今天的慢车旅程吧~~

2016/5/7

10

HDOJ_1008: Elevator

2016/5/7

11

题目评述:
这是2004浙江省赛最简单的一题,当时训练水 平相对较高的学校基本上10分钟之内解决该题, 这是一个没有算法的简单模拟题目。 入门训练的好选择~

2016/5/7

12

A+B for Polynomials
? ? ? ? ?

Sample Input 2 1 2.4 0 3.2 2 2 1.5 1 0.5 Sample Output 3 2 1.5 1 2.9 0 3.2 本题数据结构?(针对不同数据特点) 本题注意事项?
13

?
?

2016/5/7

HDOJ_1108 最小公倍数
?

?

?

? ?

给定两个正整数,计算这两个数的最小公 倍数。 Input: 10 14 Output: 70 思考:如何求最小公倍数(LCM)? LCM => GCD
2016/5/7 14

GCD求解过程
10
14 x x

10
10 4

2 x=2 4 x
2016/5/7

10 4
x
15

欧几里德算法
? ? ? ? ? ? ?

?
? ?

int gcd(int da,int xiao) { int temp; while (xiao!=0) { temp=da%xiao; da=xiao; xiao=temp; 思考: } 递归的形式如何写? return(da); }
16

2016/5/7

HDOJ_1061 Rightmost Digit
?

Given a positive integer N, you should output the most right digit of N^N (1<=N<=1,000,000,000).

? ?

3 4
7 6
2016/5/7 17

? ?

HDOJ_1061 Rightmost Digit
? ? ?

数据规模? 很大 暴力方法? 该打 基本思路? 规律

2016/5/7

18

HDOJ_2035 人见人爱A^B
?

? ?

求A^B的最后三位数表示的整数 (1<=A,B<=10000) 2 3 12 6 8 984
2016/5/7 19

?

?

HDOJ_2035 人见人爱A^B
?
? ? ? ?

最暴力的暴力? 改进的暴力? 如果: (1<=A,B<=100000000)怎么办? 二分加速(快速幂)?

2016/5/7

20

HDOJ_2035 人见人爱A^B
?
? ? ?

?
? ? ? ? ?

快速幂递归实现: int power(int a, int n){ int ans; if(n==0) ans=1; else { ans=power(a*a, n/2); if(n%2==1) ans*=a; } return ans; }

2016/5/7

21

HDOJ_2035 人见人爱A^B
?
? ? ?

?
? ? ? ? ?

快速幂非递归实现(循环+位运算) int power(int a, int n){ int ans=1; while(n){ if(n&1) ans=*a; // n&1 可以替换成? a*=a; n>>1; // n>>1 可以替换成? } return ans; }

2016/5/7

22

1021 Fibonacci Again

2016/5/7

23

题目分析:
? ? ? ?

能被3整除的整数的特点? 如果两个数的和能被3整除,这两个数有什么 特点? 关于“和”能否被3整除,这两个数一共有多 少种组合? 会不会出现某连续两项和后面连续两项相等 的情况?如果出现,能得到什么信息?

还要看程序吗?
2016/5/7 24

Hdoj_1021程序清单:
? ? ? ? ? ?

?
? ? ? ?

#include<stdio.h> int main() { long n; scanf("%ld",&n) ; if (n%8==2 || n%8==6) printf("yes\n"); else printf("no\n"); return 0; }
2016/5/7 25

HDOJ_1005: Number Sequence

2016/5/7

26

Question:

暴力(Brute-Force) 能解决问题吗?

2016/5/7

27

题目分析:
对于这种题目,千万不能蛮干!实际上, 有经验的同学看到本题目的数据规模,很快就 能知道:这类题目有规律可循。

2016/5/7

28

现在对这题有什么想法

???
2016/5/7 29

附:非典型数学题
?
?

HDOJ_1205 吃糖果
Gardon吃糖果时有个特殊的癖好,就是不喜欢 将一样的糖果放在一起吃,喜欢先吃一种,下 一次吃另一种;可是Gardon不知道是否存在一 种吃糖果的顺序使得他能把所有糖果都吃完? 请你写个程序帮忙计算一下 对于每组数据,输出一行,包含一个"Yes"或者 "No"。
2016/5/7 30

?

请自己仔细分析...
?

哪位同学做个陈述?

2016/5/7

31

课后任务:
完成在线练习:
201403《ACM程序设计》作业(2)—— 刘春英老师

特别提醒:
作业务必尽力完成(第一次的作 业尚未完成的,一定要补上~) 作业密码:helloworld
2016/5/7 32

Welcome to HDOJ

Thank You ~
2016/5/7 33


网站首页 | 网站地图
All rights reserved Powered by 海文库 haihongyuan.com
文档资料库内容来自网络,如有侵犯请联系客服。3088529994@qq.com