【剑指offer之求1+2+...+n】九度OJ-1506-求1+2+3+...+n

2024-08-27 01:58
文章标签 +...+ 九度 offer 之求 oj 1506

本文主要是介绍【剑指offer之求1+2+...+n】九度OJ-1506-求1+2+3+...+n，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目链接】：九度OJ-1506-求1+2+3+…+n
【题目描述】：
题目 1506：求1+2+3+…+n
时间限制：1 秒内存限制：128 兆特殊判题：否提交：1857解决：1060
题目描述：
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
输入：
输入可能包含多个测试样例。
对于每个测试案例，输入为一个整数n(1<= n<=100000)。
输出：
对应每个测试案例，
输出1+2+3+…+n的值。
样例输入：
3
5
样例输出：
6
15
【思路】这道题很考察发散思维，具体参见如下：
这里写图片描述
这里写图片描述
这里给出四钟解法，如果还有其他的欢迎大家补充~
【解法一】利用构造函数求解
我们仍然围绕循环做文章，循环只是让相同的代码重复执行n遍而言，我们完全可以不用for和while来达到这个效果，比如我们先定义一个类型，接着创建n个该类型的实例，那么这个类型的构造函数将确定会被调用n 次。我们可以将与累加相关的代码放到构造函数中，代码如下：

// ====================方法一===================
class temp
{
public:temp() { ++n; sum += n; }static void reset() {n=0; sum=0;}static unsigned int GetSum() {return sum;}
private:static unsigned int n;static unsigned int sum;
};
unsigned int temp::n = 0;
unsigned int temp::sum = 0;
unsigned int sum_solution1(unsigned int n)
{temp::reset();temp *a = new temp[n];delete []a;a = NULL;return temp::GetSum();
}

【解法二】利用虚函数求解
我们同样也可以围绕递归做文章。既然不能在一个函数中判断是不是应该终止递归，那么我们不妨定义两个函数：一个函数充当递归函数的角色，另一个函数处理递归的情况，我们需要做的就是在两个函数里二选一。从二选一我们很自然地想到布尔变量，比如值为true{1}的时候调用第一个函数，值为false的时候调用第二个函数，那现在的问题是如何把数值变量n换成布尔值，如果对n连续做两次反运算，即!!n那么非零的n转换为true，0转换为false。有了上述分析，我们再来看下面的代码：


// ====================方法二===================
class A;
A* array[2];
class A
{
public:virtual unsigned int sum(unsigned int n){return 0;}
};
class B: public A
{
public:virtual unsigned int sum(unsigned int n){return array[!!n]->sum(n-1)+n;}
};
int sum_solution2(int n)
{A a;B b;array[0]= &a;array[1]= &b;int value = array[1]->sum(n);return value;
}

这种思路是用虚函数来实现的选择。当n！=0时调用函数B：：sum;否则调用函数A：：sum。

【解法三】利用函数指针求解
在纯C语言的编程环境中，我们不能使用函数，此时可以用函数指针来模拟，这样代码可能还更加直观：


// ====================方法三===================
typedef unsigned int (*fun)(unsigned int);
unsigned int solution3_temp(unsigned int n)
{return 0;
}
unsigned int sum_solution3(unsigned int n)
{static fun f[2] = {solution3_temp,sum_solution3};return n + f[!!n](n-1);
}

【解法四】利用模板类型求解
另外我们还可以让编译器帮助完成类似递归的计算代码如下：

// ====================方法四===================
template <unsigned int n> struct sum_solution4
{enum value{N = sum_solution4<n-1>::N+n};
};
template <> struct sum_solution4<1>
{enum value { N = 1};
};
template <> struct sum_solution4<0>{enum value { N = 0};
};

【说明】：强调内容 sum_solution4<100>::N 就是求1+2+…+100的结果，当编译器看到sum_soution4<100>时，就会为模板类sum_solution4 以参数100生成该类型的代码。但以100为参数的类型需要得到以99为参数的类型，因为sum_solution4<100>::N=sum_solution4<99>::N+100.这个过程会一直到参数为1的类型，由于该类型已经显示定义，编译器无须生成，递归编译到此结束。由于这个过程是在编译过程中完成的，因此要求输入n必须是在编译期间就能确定的常量，不能动态输入，这是该方法最大 确定，而且编译器对递归编译代码的递归深度有限制的，也就是要求n不能太大。

完整测试代码：

/*********************************
*   Date：2017-04-15 21:40
*   Author：herongwei
*   Problem: 题目1506：求1+2+3+...+n
*   Source：http://ac.jobdu.com/problem.php?pid=1506  【剑指Offer 】
*   Result：AC
**********************************/
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <set>
#include <stack>
#include <math.h>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const int maxm = 55;
const LL MOD = 999999997;
int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
inline int read()
{int  c=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}return c*f;
}
// ====================方法一===================
class temp
{
public:temp() { ++n; sum += n; }static void reset() {n=0; sum=0;}static unsigned int GetSum() {return sum;}
private:static unsigned int n;static unsigned int sum;
};
unsigned int temp::n = 0;
unsigned int temp::sum = 0;
unsigned int sum_solution1(unsigned int n)
{temp::reset();temp *a = new temp[n];delete []a;a = NULL;return temp::GetSum();
}// ====================方法二===================
class A;
A* array[2];
class A
{
public:virtual unsigned int sum(unsigned int n){return 0;}
};
class B: public A
{
public:virtual unsigned int sum(unsigned int n){return array[!!n]->sum(n-1)+n;}
};
int sum_solution2(int n)
{A a;B b;array[0]= &a;array[1]= &b;int value = array[1]->sum(n);return value;
}// ====================方法三===================
typedef unsigned int (*fun)(unsigned int);
unsigned int solution3_temp(unsigned int n)
{return 0;
}
unsigned int sum_solution3(unsigned int n)
{static fun f[2] = {solution3_temp,sum_solution3};return n + f[!!n](n-1);
}// ====================方法四===================
template <unsigned int n> struct sum_solution4
{enum value{N = sum_solution4<n-1>::N+n};
};
template <> struct sum_solution4<1>
{enum value { N = 1};
};
template <> struct sum_solution4<0>
{enum value { N = 0};
};
// ====================测试代码===================
void Test(int n,int expected)
{printf("Test for %d begin:\n",n);if(sum_solution1(n) == expected)printf("solution1 passed.\n");elseprintf("solution1 failed.\n");if(sum_solution2(n) == expected)printf("solution2 passed.\n");elseprintf("solution2 failed.\n");if(sum_solution3(n) == expected)printf("solution3 passed.\n");elseprintf("solution3 failed.\n");
}void Test1()
{const unsigned int number = 1;int expected = 1;Test(number, expected);if(sum_solution4<number>::N == expected)printf("solution4 passed.\n");elseprintf("solution4 failed.\n");
}void Test2()
{const unsigned int number = 5;int expected = 15;Test(number, expected);if(sum_solution4<number>::N == expected)printf("solution4 passed.\n");elseprintf("solution4 failed.\n");
}void Test3()
{const unsigned int number = 10;int expected = 55;Test(number, expected);if(sum_solution4<number>::N == expected)printf("solution4 passed.\n");elseprintf("solution4 failed.\n");
}void Test4()
{const unsigned int number = 0;int expected = 0;Test(number, expected);if(sum_solution4<number>::N == expected)printf("solution4 passed.\n");elseprintf("solution4 failed.\n");
}int main()
{//freopen("in.txt","r",stdin);Test1();Test2();Test3();Test4();return 0;
}/* /solution/
Test for 1 begin:
solution1 passed.
solution2 passed.
solution3 passed.
solution4 passed.
Test for 5 begin:
solution1 passed.
solution2 passed.
solution3 passed.
solution4 passed.
Test for 10 begin:
solution1 passed.
solution2 passed.
solution3 passed.
solution4 passed.
Test for 0 begin:
solution1 passed.
solution2 passed.
solution3 passed.
solution4 passed./solution*/

这篇关于【剑指offer之求1+2+...+n】九度OJ-1506-求1+2+3+...+n的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1110307。

相关文章

20190315 把整理和培养自己当作一生的事业，而不是局限在找工作拿offer。

20190315 把整理和培养自己当作一生的事业，而不是局限在找工作拿offer。

把整理和培养自己当作一生的事业，而不是局限在找工作拿offer，做有本事的人。 来东南读研半年了，明显感觉自己掌握的不过是书本知识级别的中上水平，垃圾收集器这些的只知道背面经，靠脑子硬记，缺乏整理和系统，一头浆糊。 现在一边做实训这个烂项目，一边刷面经，一边刷剑指offer，想投些大公司的实习，又觉得还没准备好，看着各 种面经，都能说个大概，但明显感觉到自己知识的不体系和不深入，**做的项目
阅读更多...
九度1077（最大序列和）

九度1077（最大序列和）

题目链接：点击打开链接 解题思路： 很经典的一道题。首先考虑一下细节问题，当序列都是0时，显然最后要输出0；当序列都是负数时，显然要输出最大的数。 细节处理完了，就可以回到正常轨道。我们开两个变量，分别保存当前的序列和与之前的最大值，我们更新当前序列和的条件是如果当前序列和是负数的时候，那我们必须更新，否则一定会使最后结果减小。更新过程中还要更新之前最大值即可。 完整代码：
阅读更多...
哈理工OJ 2179(深搜)

哈理工OJ 2179(深搜)

组合 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 7(5 users)Total Accepted: 6(5 users)Rating: Special Judge: No Description 给出一个正整数N，从集合{1,2,3..N} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整
阅读更多...
每日OJ_牛客_求和（递归深搜）

每日OJ_牛客_求和（递归深搜）

目录 牛客_求和（递归深搜） 解析代码 牛客_求和（递归深搜） 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数，如果累加和大于等于目标，结束递归。此时如果累加和正好等于目标，则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程，找到所有的组合。 #include <iostream>#include <cmath>#in
阅读更多...
【简历】25届南京某一本JAVA简历：简历通过率还好，但是拿不到OFFER

【简历】25届南京某一本JAVA简历：简历通过率还好，但是拿不到OFFER

注：为保证用户信息安全，姓名和学校等信息已经进行同层次变更，内容部分细节也进行了部分隐藏 简历说明 今天看一份25届南京某一本大学的Java简历。 这个简历呢，学校是一本。我们说上来先要定校招层次，这个层次就按照中厂来讲。因为现在很多的双非一本目标都是在中厂。 这个同学有个实习经历，一本有八成的同学主项目都是重复的。HR他只能看到项目重不重复，要点对不对他不知道，就从这个角度来看，这位同学
阅读更多...
所以说读者们才是最优秀的 | 某读者喜提offer(+85%)后的分享

所以说读者们才是最优秀的 | 某读者喜提offer(+85%)后的分享

点击上方蓝色字体，选择“设为星标” 回复”资源“获取更多资源 这是小编的一个读者喜提offer后在群里做的分享，文中隐藏了读者的个人隐私信息，小编这里把他的面经分享出来供大家学习。  群友们看到后都纷纷表示【我酸了，现在我就是个柠檬精系列】。 小编现在也是个柠檬精????????????????????????????????。 小编现在是群里最菜的了。     关于如何学习/准备面试的总结
阅读更多...
剑指offer——替换字符

剑指offer——替换字符

/*** 剑指offer* 替换字符*/import java.util.Scanner;public class Solution {public String replaceSpace(StringBuffer str) {String s=str.toString();StringBuilder st=new StringBuilder(); for(int i=0;i<s.leng
阅读更多...
剑指offer——第一次只出现一次的字符

剑指offer——第一次只出现一次的字符

/*** */package interview35;/*** 第一次只出现一次的字符* 在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)中找到第一个只出现一次的字符,并返回它的位置*@author: Administrator*@date: 2017-1-9 下午07:34:07*/import java.util.Scanner;public class Solutio
阅读更多...
OJ-0905

OJ-0905

题目 示例1： 输入：10 10 56 34 99 1 87 8 99 3 255 6 99 5 255 4 99 7 255 2 99 9 255 213 4输出：99 示例2： 输入：10 10 255 34 0 1 255 8 0 3 255 6 0 5 255 4 0 7 255 2 0 9 255 213 5输出：255 import java.util.
阅读更多...
ssh登录服务器报错“no matching host key type found. Their offer: ssh-rsa,ssh-dss”解决方法

ssh登录服务器报错“no matching host key type found. Their offer: ssh-rsa,ssh-dss”解决方法

这个错误表明你尝试使用 ssh 连接到远程服务器时，客户端和服务器之间没有匹配的 host key 类型。具体来说，远程服务器提供了 ssh-rsa 和 ssh-dss 类型的 host key，但你的 SSH 客户端配置可能不再支持这些较旧的算法。最近的 OpenSSH 版本默认禁用了不够安全的算法，如 ssh-rsa 和 ssh-dss。 解决方法 临时启用 ssh-rsa： 你可以在
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2