【剑指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。

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

九度1077(最大序列和)

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

哈理工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_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

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

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

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

点击上方蓝色字体,选择“设为星标” 回复”资源“获取更多资源 这是小编的一个读者喜提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——第一次只出现一次的字符

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

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 连接到远程服务器时,客户端和服务器之间没有匹配的 host key 类型。具体来说,远程服务器提供了 ssh-rsa 和 ssh-dss 类型的 host key,但你的 SSH 客户端配置可能不再支持这些较旧的算法。最近的 OpenSSH 版本默认禁用了不够安全的算法,如 ssh-rsa 和 ssh-dss。 解决方法 临时启用 ssh-rsa: 你可以在