ACM-习题-c语言-骨牌铺方格

一道编程题的探索北京 李兆伟工人铺人行道，人行道是一段2×n 的矩形区域，现有规格为1×1的地板和1×2的地砖若干，问用这些地砖铺满这个2×7的区域共有多少种不同的拼法？用这些地砖铺满这个2×n 的区域共有多少种不同的拼法？【答案】2356【解析】设要铺n 个格子的方法数为n a ，铺满2n ⨯的矩形区域方法数为2n a 。

显然11a =，22a =。

本题即为求14a 的值。

3n =时，如下图所示。

若先铺第一个格子，方法数等价于2a ；若先铺2个格子，方法数等价于1a 。

3123a a a =+=。

4n =时，如下图所示。

第一步有3种铺法，方法数分别等价于3a 、2a 、2a 。

43227a a a a =++=。

5n =时，如下图所示。

第一步有2种铺法，方法数分别等价于3a 、4a 。

53410a a a =+=。

6n =时，如下图所示。

根据前两步的铺法可分为以下4类，方法数分别等价于5a 、4a 、3a 、2a 。

6234522a a a a a =+++=。

根据上述规律，我们对于n ()n ＞4取不同奇偶性进行分开讨论。

① 当n 为奇数时，第一步有如下两种分类：分别对应方法数为1n a −，2n a −。

所以有递推式12n n n a a a −−=+（n 为奇数）。

② 当n 为偶数时，前两步有如下四种分类：分别对应方法数为1n a −，2n a −，3n a −，4n a −。

所以有递推式1234n n n n n a a a a a −−−−=+++（n 为偶数）。

综上，我们得出完整递推式n ＞4时，121234,,n n n n n n n a a n a a a a a n −−−−−−+⎧⎪=⎨+++⎪⎩为奇数为偶数。

根据递推式，列出表格如下：所以本题有2356种不同的拼法。

【拓展】本题递推式有更简洁的解答，在题友“Lin-匯丰”的帮助下写出。

acm试题及答案c1. 问题描述编写一个程序，计算给定整数序列中所有正整数的和。

2. 输入格式第一行包含一个整数N，表示序列中整数的数量。

第二行包含N个整数，用空格分隔。

3. 输出格式输出一个整数，表示所有正整数的和。

4. 示例输入：```51 2 3 -4 5```输出：```11```5. 问题分析本题要求计算给定整数序列中所有正整数的和。

首先，需要读取输入序列，然后遍历序列中的每个整数，判断其是否为正数，如果是，则将其累加到总和中。

6. 算法实现#include <stdio.h>int main() {int N, sum = 0;scanf("%d", &N);int number;for (int i = 0; i < N; i++) { scanf("%d", &number);if (number > 0) {sum += number;}}printf("%d\n", sum);return 0;}```7. 测试测试1：输入：```3-1 2 3```输出：```5```测试2：```40 -2 3 -4```输出：```3```8. 注意事项- 确保读取的整数数量与输入的第一行相符。

- 考虑边界情况，如序列中没有正整数的情况。

- 程序应能正确处理负数和零。

1106 是否阶乘之和？Description输入一整数N，判断是否可以表示成一个或几个不同正整数的阶乘之和。

Input输入一个整数N。

Output对应输入，若可以表示，输出YES，否则输出NOSample Input3Sample OutputYES1135 求矩形个数Description有一个大的矩形由（M*N）个小的矩形组成。

求一共有多少个矩形。

Input输入两个整数，分别代表M,N (0 <= N,M < 100) 。

Output输出矩形的个数。

Sample Input2 2Sample Output91138 行注释清除Description给出一个C++源程序代码。

请将其中的注释去掉。

Input输入若干行源程序代码（含注释），注释全部采用行注释的形式，即用双斜杠开头的。

Output输出去掉注释后的代码，其余不变。

Sample Input//======================// simplest program//======================#include<stdio.h>using namespace std;//----------------------int main(){cout<<”hello world!\n”;}//---------------------Sample Output#include<stdio.h>using namespace std;int main(){cout<<”hello world!\n”;}1143 汉诺塔Description汉诺塔问题是这样的：有3根柱子a,b,c，其中a柱上有64个盘子，盘子大小不等，大的在下，小的在上。

要求把这64个盘子从a柱移到c柱上，在移动过程中可以借助b柱，每次只允许移动一个盘子，且在移动过程中在三根柱子上都保持大盘在下，小盘在上。

OJ输入输出训练：HDOJ 1089 ～HDOJ 1096一、C语言基础练习1001 计算两点间的距离HDOJ 2001 1002 第几天？HDOJ 2005 1003 平方和与立方和HDOJ 2007 1004 水仙花数HDOJ 2010 1005 素数判定HDOJ 2012 1006 数列有序！HDOJ 2019 1007 发工资咯：）HDOJ 2021 1008 海选女主角HDOJ 2022 1009 求平均成绩HDOJ 2023 1010 汉字统计HDOJ 2030 1011 进制转换HDOJ 2031 1012 杨辉三角HDOJ 2032 1013 人见人爱A+B HDOJ 2033 1014 人见人爱A-B HDOJ 2034 1015 亲和数HDOJ 2040 1016 Sum Problem HDOJ 1001 1017 A + B Problem II HDOJ 1002 1018 Let the Balloon Rise HDOJ 1004 1019 Elevator HDOJ 1008 1020 FatMouse' Trade HDOJ 1009 1021 As Easy As A+B HDOJ 1040 1022 The Hardest Problem Ever HDOJ 1048 1023 Climbing Worm HDOJ 1049 1024 Text Reverse HDOJ 1062 1025 An Easy Task HDOJ 1076 1026 What Is Your Grade? HDOJ 1084二、简单数学题1001 最小公倍数HDOJ 1108 1002 Least Common Multiple HDOJ 1019 1003 人见人爱A^B HDOJ 0235 1004 Rightmost Digit HDOJ 1061 1005 Fibonacci Again HDOJ 1021 1006 Number Sequence HDOJ 1005 1007 The area HDOJ 1071 1008 吃糖果HDOJ 1205 1009 Sky数HDOJ 2097 1010 Box of Bricks HDOJ 20881011 简易版之最短距离HDOJ 20831012 Fibbonacci Number HDOJ 20701013 Coin Change HDOJ 20691014 A + B Again HDOJ 20571015 Lowest Common Multiple Plus HDOJ 20281016 Can you solve this equation? HDOJ 21991017 Strange fuction HDOJ 28991018 Pseudoprime numbers HDOJ 19051019 Delta-wave HDOJ 10301020 月之数HDOJ 25021021 又见GCD HDOJ 25041022 找新朋友HDOJ 12861023 七夕节HDOJ 12151024 完数HDOJ 1406三、递推求解1001 超级楼梯HDOJ 20411002 不容易系列之二HDOJ 20421003 一只小蜜蜂... HDOJ 20441004 不容易系列之(3)——LELE的RPG难题HDOJ 20451005 骨牌铺方格HDOJ 20461006 折线分割平面HDOJ 20501007 母牛的故事HDOJ 20181008 下沙的沙子有几粒？HDOJ 12671009 自共轭Ferrers图HDOJ 12461010 汉诺塔II HDOJ 12071011 悼念512汶川大地震遇难同胞——重建希望小学HDOJ 2190 1012 Children’s Queue HDOJ 12971013 Tiling_easy version HDOJ 25011014 统计问题HDOJ 25631015 Buy the Ticket HDOJ 11331016 Game of Connections HDOJ 11341017 Computer Transformation HDOJ 10411018 Children’s Queue HDOJ 12971019 The Number of Paths HDOJ 12931020 "下沙野骆驼"ACM夏令营HDOJ 129四、简单典型DP1001 数塔HDOJ 20841002 Super Jumping! Jumping! Jumping! HDOJ 10871003 免费馅饼HDOJ 11761004 Common Subsequence HDOJ 11591005 搬寝室HDOJ 14211006 Humble Numbers HDOJ 10581007 Max Sum HDOJ 10031008 Max Sum Plus Plus HDOJ 10241009 FatMouse's Speed HDOJ 11601010 Bone Collector HDOJ 26021011 Piggy-Bank HDOJ 11141012 I NEED A OFFER! HDOJ 12031013 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活HDOJ 2191 1014 Coins HDOJ 2844五、简单博弈1001 Brave Game HDOJ 18461002 Good Luck in CET-4 Everybody! HDOJ 18471003 Fibonacci again and again HDOJ 18481004 Rabbit and Grass HDOJ 18491005 Being a Good Boy in Spring Festival HDOJ 18501006 kiki's game HDOJ 21471007 Public Sale HDOJ 21491008 悼念512汶川大地震遇难同胞——选拔志愿者HDOJ 21881009 丑数游戏1010 YLF's Game六、半程测试1001 CD HDOJ 37631002 Alaska HDOJ 37641003 Celebrity Split HDOJ 37651004 Knight's Trip HDOJ 37661005 Paintball HDOJ 37671006 Shopping HDOJ 37681007 Stack Machine HDOJ 37691008 Ideas HDOJ 37701009 HST HDOJ 37711010 Tunnelling the Earth H DOJ 3772七、母函数1001 Ignatius and the Princess III HDOJ 10281002 Square Coins HDOJ 13981003 Holding Bin-Laden Captive! HDOJ 10851004 Big Event in HDU HDOJ 11711005 Fruit HDOJ 21521006 The Balance HDOJ 1709八、并查集1001 How Many Tables HDOJ 1213 1002 小希的迷宫HDOJ 1272 1003 Is It A Tree? HDOJ 1325 1004 More is better HDOJ 1856 1005 Constructing Roads HDOJ 1102 1006 畅通工程HDOJ 1232 1007 还是畅通工程HDOJ 1233 1008 畅通工程HDOJ 1863 1009 畅通工程再续HDOJ 1875 1010 继续畅通工程HDOJ 1879共26 + 24 + 20 + 14 + 10 + 6 + 10 = 110 题。

HDU2046⾻牌铺⽅格递推C语⾔
题⽬：
知道应该⽤递归递推来做，但是⼀直找不到规律……拖了好久，终于决定今天做完。

苦思⽆果搜题解，发现代码只有⼏⾏…… 递推递归果然神奇啊
思路：f(1)=1,f(2)=2,f(3)=5，当有n个⽅格的时候，有两种铺法：
１）先铺好n-1个格，有f(n-1)个⽅法，再铺第n层的时候只有⼀种⽅法，所以总⽅法是１*f(n-1);
2)先铺好n-2格，有f(n-2)个⽅法，再铺后⾯两层的时候只能两个都横着铺（否则与第⼀种情况重复），所以也只有⼀种情况，总⽅法数是1*f(n-2)
再没有其他情况了。

推出f(n)=f(n-1)+f(n-2)
提交情况： 2次TLE，两次WA
AC code：
View Code
1#include <stdio.h>
2#include <stdlib.h>
3int main () {
4int n;
5int i;
6 __int64 a[60] = {0, 1, 2};
7for (i = 3; i <= 51; i++)
8 a[i] = a[i - 1] + a[i - 2];
9while (~scanf ("%d", &n))
10 printf ("%I64d\n", a[n]);
11//system ("pause");
12return0;
13}
先开始写了⼀个⼦函数递归，于是超时了，改⽤数组写，a[n]开成了int型，溢出了，于是WA了……
这种找规律的题还是要多多练习才⾏啊！。

c语言方格取数-回复C语言方格取数方格取数是一种经典的问题。

在一个n×m的方格中，每个格子都有一个正整数。

我们需要从左上角的格子开始，每次只能向下或向右移动一个格子，直到到达右下角的格子。

我们要找到一条路径，使得沿途取到的数的和最大。

这个问题可以使用动态规划的方法来解决。

我们定义一个二维数组f[i][j]来表示从左上角到达格子(i,j)的路径上所取数的最大和。

则有以下递推关系式：f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j]其中a[i][j]代表格子(i,j)中的数。

根据这个递推关系式，我们可以从左上角一步步计算到右下角的路径上所取数的最大值。

下面我们用一个具体的例子来解释这个问题：假设有一个5×5的方格，其中每个格子内的数如下所示：3 7 9 2 79 8 3 5 51 7 9 8 53 8 64 106 3 97 8我们可以通过动态规划的方法来求解从左上角到右下角的最大路径和。

首先，初始化f[0][0]为a[0][0]，即f[0][0] = 3。

然后，根据递推关系式，我们可以得到：f[0][1] = f[0][0] + a[0][1] = 3 + 7 = 10f[1][0] = f[0][0] + a[1][0] = 3 + 9 = 12接下来，我们可以计算第一行和第一列的最大路径和，即：f[0][2] = f[0][1] + a[0][2] = 10 + 9 = 19f[0][3] = f[0][2] + a[0][3] = 19 + 2 = 21f[0][4] = f[0][3] + a[0][4] = 21 + 7 = 28f[1][0] = f[0][0] + a[1][0] = 12 + 9 = 21f[2][0] = f[1][0] + a[2][0] = 21 + 1 = 22f[3][0] = f[2][0] + a[3][0] = 22 + 3 = 25f[4][0] = f[3][0] + a[4][0] = 25 + 6 = 31接下来，我们可以计算其他格子的最大路径和，即：f[1][1] = max(f[0][1], f[1][0]) + a[1][1] = max(10, 21) + 8 = 29f[1][2] = max(f[0][2], f[1][1]) + a[1][2] = max(19, 29) + 3 = 32f[1][3] = max(f[0][3], f[1][2]) + a[1][3] = max(21, 32) + 5 = 37f[1][4] = max(f[0][4], f[1][3]) + a[1][4] = max(28, 37) + 5 = 42f[2][1] = max(f[1][1], f[2][0]) + a[2][1] = max(29, 22) + 7 = 36f[2][2] = max(f[1][2], f[2][1]) + a[2][2] = max(32, 36) + 9 = 45f[2][3] = max(f[1][3], f[2][2]) + a[2][3] = max(37, 45) + 8 = 53f[2][4] = max(f[1][4], f[2][3]) + a[2][4] = max(42, 53) + 5 = 58依此类推，我们可以计算出所有格子的最大路径和。

一、概述C语言是一种广泛应用于系统软件开发和其他应用程序的程序设计语言，它具有高效、灵活、功能强大等特点，因而备受程序员的青睐。

而九九乘法表作为学习编程的基础练习题，可以帮助程序员熟悉循环、条件语句等基本编程知识，并通过实践加深对C语言编程的理解。

二、九九乘法表1. 九九乘法表是指将1-9的数字两两相乘所得到的结果表格，其中横轴和纵轴分别代表乘法表中的乘数和被乘数。

九九乘法表能够全面展示1-9的乘法关系，有助于理解整数相乘的规律。

2. 在C语言中，我们可以通过嵌套循环来实现九九乘法表的打印。

具体来说，外层循环控制被乘数，内层循环控制乘数，通过循环嵌套，依次输出每一对乘积。

3. 九九乘法表具有固定的格式，每个乘积占据固定的位置，因此在编写C语言程序时，需要控制输出格式，使得乘法表整齐美观、易于阅读。

三、C语言编程实现1. 我们需要在C语言中编写一个嵌套循环的程序，外层循环控制被乘数，内层循环控制乘数。

2. 在内层循环中，我们可以使用printf函数打印乘积，并在乘积之间添加空格，使得乘法表整齐排列。

3. 我们需要注意控制每行的输出个数，确保乘法表的格式正确，不会出现错位或者空行的情况。

四、C语言编程实例代码下面给出一个简单的C语言编程示例，展示了如何使用嵌套循环打印九九乘法表：#include <stdio.h>int m本人n() {int i, j;for (i = 1; i <= 9; i++) {for (j = 1; j <= i; j++) {printf("d * d = 2d\t", j, i, i * j);}printf("\n");}return 0;}五、代码解析1. 在上面的示例代码中，我们首先定义了两个变量i和j，分别代表被乘数和乘数。

2. 外层循环使用i来控制被乘数，内层循环使用j来控制乘数。

3. 在内层循环中，我们使用printf函数输出乘积，并且通过制表符\t和格式化输出控制符2d来控制格式，使得乘法表对齐美观。

Problem Description有一个大小是2 x n 的网格，现在需要用2种规格的骨牌铺满，骨牌规格分别是2 x 1 和2 x 2，请计算一共有多少种铺设的方法。

Input输入的第一行包含一个正整数T（T<=20），表示一共有T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示网格的大小是2行N列。

Output输出一共有多少种铺设的方法，每组数据的输出占一行。

Sample Input32812Sample Output31712731答案：#include <stdio.h>void main(){int num,n,n_1,n_2,t,i;for(;scanf(" %d",&num) != EOF;)for(;num-- && scanf(" %d",&n) != EOF;printf("%d\n",n==1?1:n_1))for(n_1=3,n_2=1,i=2;i<n;i++){t=n_1;n_1+=2*n_2;n_2=t;}}Problem Description对于四川同胞遭受的灾难，全国人民纷纷伸出援助之手，几乎每个省市都派出了大量的救援人员，这其中包括抢险救灾的武警部队，治疗和防疫的医护人员，以及进行心理疏导的心理学专家。

根据要求，我校也有一个奔赴灾区救灾的名额，由于广大师生报名踊跃，学校不得不进行选拔来决定最后的人选。

经过多轮的考核，形势逐渐明朗，最后的名额将在“林队”和“徐队”之间产生。

但是很巧合，2个人的简历几乎一模一样，这让主持选拔的8600很是为难。

无奈，他决定通过捐款来决定两人谁能入选。

选拔规则如下：1、最初的捐款箱是空的；2、两人轮流捐款，每次捐款额必须为正整数，并且每人每次捐款最多不超过m元(1<=m<=10)。

3、最先使得总捐款额达到或者超过n元（0<n<10000）的一方为胜者，则其可以亲赴灾区服务。