五、六年级学案 ：
1.作业点评：用递归算法完成 http://116.198.200.119:5000/homework_Show.asp?id=1223
题目：
1.简单数列5
已知一数列：1,3,3,5,5,5,7,7,7,7,9,9,9,9,9,11,11,11,11,11,11,11.....请根据规律求出第n项的值。例如：n=4 项时，其值为5,n=11时，其值为9.
输入格式
一个自然数n,(0<n<1000)
输出格式
一个整数，即第n项的值。
样例输入
4
样例输入
5
参考程序：
#include<iostream>
using namespace std;
int n;
int f(int k,int x,int y,int z){//k表示当前来到数列第k项，x表示当前项处于第x周期，y是当前项处于当前周期中的第y项，z表示当前项的值
//cout<<z<<" ";
if(k==n)return z;
if(x==y)f(k+1,x+1,1,z+2);//如果当前周期内项数已填满，则要到下一周期的第一项
else
f(k+1,x,y+1,z);//如果当前周期未满，则来到当前周期中的下一项
}
int main(){
cin>>n;
cout<<f(1,1,1,1);
return 0;
}
2.采药
【问题描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
【输入文件】
输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据，M <= 10
对于全部的数据，M <= 100。
参考程序：
#include<iostream>
#include<cstdio>
using namespace std;
int n,t,a[101]={0},v[101]={0},vm=0 ;
int f(int x,int s,int y){
if(x>n){if (y>vm)vm=y;
return 0;
}
if(s>=a[x]) {
f(x+1,s-a[x],y+v[x]);
}
f(x+1,s,y);
}
int main(){
freopen("p1105.in","r",stdin);
freopen("p1105.out","w",stdout);
scanf("%d %d\n",&t,&n);
int i;
for(i=1;i<=n;i++){
scanf("%d %d",&a[i],&v[i]);
}
f(1,t,0);
printf("%d",vm);
fclose(stdin);
fclose(stdout);
}
2.课堂测试：
1.分解质因数
(prime.pas/c/cpp)
【问题描述】
分解质因数是把合数用几个质数相乘的形式表现出来,一般先用这个合数最小的那个因数（是质数的因数）去除,商如果是合数,就继续除：商如果是质数,就写成商乘除数的形式 30＝2*3*5; 36=2*2*3*3; 45=3*3*5; 50=2*5*5 你看,例如把30来分解质因数,它最小的因数是（一定用合数除）2,30除以2等于15,15是合数,就继续除,15最小的因数是3,15除以3等于5,5是质数,就不用继续除了.接着把分解出的几个数字写成连乘的形式,即：30＝2*3*5.
现在的问题是，给出一个正整数N，如果它是质数，则输出它等于其本身，如果它不是质数，则输出它分解质因数的式子，见下面输入输出样例。
【输入】
只有一个正整数N（2=<N<=10000）。
【输出】
只有一行，一个符合上面要求的式子。
【输入输出样例1】
36
36=2*2*3*3
【输入输出样例2】
7
7=7
参考程序：
#include<bits/stdc++.h>
using namespace std;
int n,s,a[100]={0};
void f(int k,int x,int y){
s=k;
if(x%y==0){
a[k]=y;
if(x/y==1)return ;
f(k+1,x/y,y);
}else
{ y++;
if(y>x)return ;
f(k,x,y);
}
}
int main(){
cin>>n;
f(1,n,2);
cout<<n<<"="<<a[1];
for(int i=2;i<=s;i++)cout<<"*"<<a[i];
return 0;
}
2.小明的排名。数学竞赛试卷批改好了，但是还没排名，老师的成绩单上只有每个学生的分数，小明知道了自己的分数，但他想知道自己的排名，你能帮他算算他排在第几名吗？
输入格式
第一行为两个数n和x，n表示全体考试的学生人数，x表示小明的分数。n和 x之间有个空格。
第2行为n个整数， 相邻两个整数之间均有一个空格。
输出格式
一个整数，表示小明的排名。
样例输入
10 79
85 67 98 92 79 85 64 79 61 72
样例输出
5
参考程序：
#include<bits/stdc++.h>
using namespace std;
int n,s,a[10000]={0};
void f(int k,int x ){
if(k>n) {
cout<<x+1;
return ;
}
if(a[k]>s)f(k+1,x+1);
else f(k+1,x);
}
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++)cin>>a[i];
f(1,0);
return 0;
}
3.已知数列：1,1,2,1,1,2,3,2,1,1,2,3,4,3,2,1,1......第3项为2，第4项为1，求第n项的值。
输入格式
一个数n,表示第n项。
输出格式
一个数，表示第n项的值。
样例输入
7
样例输出
3
参考程序：
#include<iostream>
using namespace std;
int n;
int f(int k,int x,int y,int z){//k表示当前来到数列第k项，x表示当前项处于第x周期，y是当前项处于当前周期中的第y项，z表示当前项的值
if(k==n)return z;
if(2*x-1==y)f(k+1,x+1,1,1);//如果当前周期内项数已填满，则要到下一周期的第一项
else
if(y<x) return f(k+1,x,y+1,z+1);//如果当处于前半周期
else return f(k+1,x,y+1,z-1);//如果当处于后半周期
}
int main(){
freopen("p1030.in","r",stdin);
freopen("p1030.out","w",stdout);
cin>>n;
cout<<f(1,1,1,1);
fclose(stdin);
fclose(stdout);
return 0;
}
4.把自然数Ｎ分解为若干个自然数之和。
输入n,输出由各自然数之和组成n的所有方案，要求先输出组成数最小的方案，并输出总方案数。
[样例1]：
输入：5
输出：
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5
sum=7
[样例2]：
输入：6
输出：
1 1 1 1 1 1
1 1 1 1 2
1 1 1 3
1 1 2 2
1 1 4
1 2 3
1 5
2 2 2
2 4
3 3
6
sum=11
参考程序：
#include <iostream>
using namespace std;
int a[100] = {1}, cnt;
void dfs(int N, int M) {
if (N == 0) {
cnt ++;
for (int i = 1; i < M; i ++) {
cout << a[i] << " ";
}
cout << "\n";
return;
}
for (int i = a[M - 1]; i <= N; i ++) {
a[M] = i;
dfs(N - i, M + 1);
}
}
int main() {
freopen("p1070.in", "r", stdin), freopen("p1070.out", "w", stdout);
int N;
cin >> N;
dfs(N, 1);
cout << "sum=" << cnt;
fclose(stdin), fclose(stdout);
return 0;
}
( 2026/10/15 17:28:58 ) |
666
