noip2014到2017初赛提高组看程序写结果、完善程序

最新推荐文章于 2020-09-15 10:33:22 发布

flymist

最新推荐文章于 2020-09-15 10:33:22 发布

阅读量1k

点赞数

分类专栏： OI

本文链接：https://blog.csdn.net/flymist/article/details/82979903

版权

OI 专栏收录该内容

26 篇文章

订阅专栏

本文解析了NOIP 2017年编程竞赛中三道典型题目，包括带循环的递归调用、求幻方及求逆序对算法，通过代码示例详细阐述了解题思路。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

提高组和普及组的不少题目是一样的

noip2017

1.带循环的递归调用
#include <iostream> 
using namespace std;
int g(int m, int n, int x) { 
    int ans = 0;
    int i;
    if (n == 1) return 1;
    for (i = x; i <= m / n; i++) 
        ans += g(m - i, n - 1, i); 
    return ans; 
} 
int main() { 
    int  t, m, n; 
    cin >> m >> n;
    cout << g(m, n, 0) << endl; 
    return 0;
}
输入：8 4
输出：_________
递归调用的时候要能够比较清晰的把下面的式子写出来
g(8,4,0)=g(8,3,0)+g(7,3,1)+g(6,3,2)=10+4+1=15
g(8,3,0)=g(8,2,0)+g(7,2,1)+g(6,2,2)=5+3+2=10
g(8,2,0)=g(8,1,0)+g(7,1,1)+g(6,1,2)+g(5,1,3)+g(4,1,4)=5
g(7,2,1)=g(6,1,1)+g(5,1,2)+g(4,1,3)=3
g(6,2,2)=g(4,1,2)+g(3,1,3)=2 
g(7,3,1)=g(6,2,1)+g(5,2,2)=3+1=4
g(6,2,1)=g(5,1,1)+g(4,1,2)+g(3,1,3)=3
g(5,2,2)=g(3,1,2)=1 
g(6,3,2)=g(4,2,2)=g(2,1,2)=1

 
2. 求幻方

17 24 1 8 15
按照它给的规则写：第一行中间是1，下一个数写在上一个数的右上面那个格（第一行的上一行是最后一行，最后一列的右面是第一列），如果右上面那个格已经填过就填它下面那个（能填右上填右上，填不了右上就填右面那个） 
 
3. 求逆序对（归并排序）


 
 
4. 模拟矩阵内45度反弹，到哪个角就是哪个
#include  <iostream>
using namespace std;
int main() { 
    int n, m;
    cin >> n >> m; 
    int x = 1;
    int y = 1; int dx = 1; int dy = 1; int cnt = 0;
    while (cnt != 2) { 
        cnt = 0;
        x= x + dx;
        y= y + dy;
        if (x == 1 || x == n) { 
            ++cnt;
            dx = -dx;
        }
        if (y == 1 || y == m) { 
            ++cnt;
            dy = -dy;
        }
    }
    cout << x << " " << y << endl; 
    return 0;
}
输入 1：4 3
输出 1：_________（2 分）
输入 2：2017 1014
输出 2：_________（3 分）
输入 3：987 321
输出 3：_________（3 分）