网站建设培训多少钱,网站开发培训光山,学校网站建设策划,企业门户网站框架设计C蓝桥杯皮亚诺曲线距离求解 一、题目概述二、解题分析2.1解题思路2.2k值范围限制 三、实现代码四、代码测试4.1蓝桥杯测试平台4.2直接传入原始输入的k值4.3限制k值大小4.4pow函数求整数高次幂存在误差4.5满分代码 附录error: ‘long long int y1’ redeclared as different kin… C蓝桥杯皮亚诺曲线距离求解 一、题目概述二、解题分析2.1解题思路2.2k值范围限制 三、实现代码四、代码测试4.1蓝桥杯测试平台4.2直接传入原始输入的k值4.3限制k值大小4.4pow函数求整数高次幂存在误差4.5满分代码 附录error: ‘long long int y1’ redeclared as different kind of symbol报错C中int类型与long long类型取值范围 一、题目概述
给定指定阶数的皮亚诺曲线以及曲线上的两个点的坐标求解两个点之间的距离曲线起点坐标规定为0,0。
一阶皮亚诺曲线如下图 k1阶的皮亚诺曲线是在k阶曲线的基础上每一个格子由一阶曲线代替而生成。例如二阶曲线如下图 三阶曲线如下图 k阶曲线的边长为3的k次幂格子总数为3的2k次幂。无论k取何值曲线的起点总为左下角坐标为0,0终点为右上角坐标为3的2k次幂-1,3的2k次幂-1。
二、解题分析
2.1解题思路
经过初步分析
如果直接求解两点间的距离那么需要求解任意两点间的详细路径难度很大可以将求两点间距离转换为求出到原点的距离然后相减k1阶曲线是在1阶曲线的基础上层层细化网格而成那么任意一点到原点的距离也可以先从宏观处入手层层细化求解。
一阶曲线按照从起点到终点的行走顺序对网格进行划分那么可分为1~9个区域如下图所示 任意k阶曲线都可以划分为上图所示的9个区域例如二阶曲线划分如下图
假设k阶曲线上的任意一点该点到原点的距离该点到所在区域起点的距离本区域之前的区域网格数累加和而该点到所在区域起点的距离又可以转换为以所在区域起点为原点的求解到原点距离的问题因此可以层层递归求解。
根据上述解题思路细化解题步骤如下
首先判断出k阶曲线上任意一点xy所在区域每个区域的边长为3的k-1次幂因此可以通过对比大小得出判断点到所在区域起点的距离如果要转换为以所在区域起点为原点的点到该原点的距离就要将区域的起点映射为区域1的起点即原点该映射不仅仅是平移可能还要旋转以二阶曲线为例区域2的起点转换为区域1的起点。区域2的起点坐标为2,3如果要转换到0,0那么就需要进行映射2-xy-3xy为区域2内的点2-x说明区域2进行了X轴方向的翻转本区域之前的区域网格数累加计算较为简单每个区域的网格数为3的2k-2次幂例如区域5之前的区域网格数累加就等于4×3的2k-2次幂。
解题步骤大致如上读者对皮亚诺曲线随阶数的增加而在形状上层层裂变的过程有一个形象的想象过程有助于理解解题步骤。
2.2k值范围限制
由于题目中说明k值范围为1~100而点的坐标的范围为不超过10的18次方显然3的100次幂超过了10的18次方同时也超过了C中long long类型可表示的范围因此不能直接将k值代入进行求解而是要先判断出在10的18次方范围内的最大k值判断代码如下
void test_k()
{int k0;long long p1;while(true){p1pow(3, k);if(p11e18)break;k;}coutkendl;coutp1endl;
}得出k值最大为38。
三、实现代码
代码使用C实现如下
#includeiostream
#includealgorithm
#includecmath
using namespace std;int k;
long long x11,y11,x12,y12;long long func01(long long x, long long y, int k)
{if(k 0) return 0;long long tmppow(3, k-1);if(x tmp y tmp) return func01(x, y, k-1);//region1 if(x tmp (y tmp y tmp*2)) return tmp*tmp func01(tmp-1-x, y-tmp, k-1);//region2if(x tmp (y tmp*2 y tmp*3)) return 2*tmp*tmp func01(x, y-tmp*2, k-1);//region3if((x tmp x tmp*2) y tmp) return 5*tmp*tmp func01(x-tmp, tmp-1-y, k-1);//region6if((x tmp x tmp*2) (y tmp y tmp*2)) return 4*tmp*tmp func01(tmp*2-1-x, tmp*2-1-y, k-1);//region5if((x tmp x tmp*2) (y tmp*2 y tmp*3)) return 3*tmp*tmp func01(x-tmp, tmp*3-1-y, k-1);//region4if((x tmp*2 x tmp*3) y tmp) return 6*tmp*tmp func01(x-tmp*2, y, k-1);//region7if((x tmp*2 x tmp*3) (y tmp y tmp*2)) return 7*tmp*tmp func01(tmp*3-1-x, y-tmp, k-1);//region8if((x tmp*2 x tmp*3) (y tmp*2 y tmp*3)) return 8*tmp*tmp func01(x-tmp*2, y-tmp*2, k-1);//region9return -1;
}int main()
{cink;cinx11y11;cinx12y12;if(k 38) k38;coutabs(func01(x11,y11,k)-func01(x12,y12,k))endl;return 0;
}此题代码并不长关键在于解题思路。
四、代码测试
4.1蓝桥杯测试平台
为测试代码正确性可以在蓝桥杯的刷题平台提交代码网址为https://www.lanqiao.cn/problems/?first_category_id1。
皮亚诺曲线距离题目编号为141如下图所示
4.2直接传入原始输入的k值
在蓝桥杯解题平台对代码进行测试当将k值直接传入递归函数时可以得到90%的分数显示10个测试实例中有一个答案错误如下图所示 在本地运行代码发现确实是因为3的100次方超出了long long类型的范围导致错误输出。
4.3限制k值大小
对k值大小进行限制采用了本文第三节中给出的代码在蓝桥杯平台提交结果依然显示10个测试实例中有一个答案错误后将该错误实例的输入数据与输出数据下载到本地测试数据如下
kx11x12y11y12100972800214282722763781912860110024270972800214336621164781912860202693276
正确输出应为191503939959914635。 在本地运行程序得到的输出为191503939959943987确实与答案不一致经过一番检查后发现是由于pow函数导致的答案错误。
4.4pow函数求整数高次幂存在误差
分别使用pow函数求3的k次幂与连续乘积计算3的k次幂测试结果的一致性代码如下
void test_pow()
{int k1;long long p1,p21;while(true){p1pow(3, k);p2*3;if(p11e18)break;k;coutp1,p2endl;}coutkendl;coutp1endl;
}输出如下图 从输出结果分析当k≥35时两种方法计算出的3的k次幂出现了不同且差异会越来越大。通过查找资料得知pow函数返回的是double类型在被强制转换为整型时会出现误差。
4.5满分代码
因此代码中不再使用pow函数而是通过连续乘积计算幂最终代码如下
#includeiostream
#includealgorithm
#includecmath
using namespace std;int k;
long long p[100];
long long x11,y11,x12,y12;long long func01(long long x, long long y, int k)
{if(k 0) return 0;//long long tmppow(3, k-1);long long tmpp[k-1];if(x tmp y tmp) return func01(x, y, k-1);//region1 if(x tmp (y tmp y tmp*2)) return tmp*tmp func01(tmp-1-x, y-tmp, k-1);//region2if(x tmp (y tmp*2 y tmp*3)) return 2*tmp*tmp func01(x, y-tmp*2, k-1);//region3if((x tmp x tmp*2) y tmp) return 5*tmp*tmp func01(x-tmp, tmp-1-y, k-1);//region6if((x tmp x tmp*2) (y tmp y tmp*2)) return 4*tmp*tmp func01(tmp*2-1-x, tmp*2-1-y, k-1);//region5if((x tmp x tmp*2) (y tmp*2 y tmp*3)) return 3*tmp*tmp func01(x-tmp, tmp*3-1-y, k-1);//region4if((x tmp*2 x tmp*3) y tmp) return 6*tmp*tmp func01(x-tmp*2, y, k-1);//region7if((x tmp*2 x tmp*3) (y tmp y tmp*2)) return 7*tmp*tmp func01(tmp*3-1-x, y-tmp, k-1);//region8if((x tmp*2 x tmp*3) (y tmp*2 y tmp*3)) return 8*tmp*tmp func01(x-tmp*2, y-tmp*2, k-1);//region9return -1;
}int main()
{cink;cinx11y11;cinx12y12;if(k 38) k38;p[0]1;for(int i 1; i k; i) p[i]p[i-1]*3;coutabs(func01(x11,y11,k)-func01(x12,y12,k))endl;return 0;
}上述代码提交后全部10个用例全部跑通。
附录
error: ‘long long int y1’ redeclared as different kind of symbol报错
初始编写上述代码时第一个点的坐标变量本来定义为x1y1代码在本地Dev-C编译器上能够正确运行但是在蓝桥杯解题平台上运行就报出该错误后经查找资料后发现cmath头文件中定义了与y1同名的函数所以导致报错因此上述代码中的变量名改为x11,y11,x12,y12。
C中int类型与long long类型取值范围
类型专用存储空间表示范围次方表示int4个字节-2,147,483,6482,147,483,647 − 2 31 -2 ^{31} −231 ~ 2 31 2 ^{31} 231-1约为10的9次方unsigned int4个字节04,294,967,2950 ~ 2 32 2 ^{32} 232-1约为10的9次方long4个字节-2,147,483,6482,147,483,647 − 2 31 -2 ^{31} −231 ~ 2 31 2 ^{31} 231-1约为10的9次方unsigned long4个字节04,294,967,2950 ~ 2 32 2 ^{32} 232-1约为10的9次方long long8个字节-9,223,372,036,854,775,8089,223,372,036,854,775,807 − 2 63 -2 ^{63} −263 ~ 2 63 2 ^{63} 263-1约为10的18次方unsigned long long8个字节018,446,744,073,709,551,6150 ~ 2 64 2 ^{64} 264-1约为10的19次方
