[数据结构与算法]【erlang】解决一个私信问题，用递归求一个奇偶分支表达式

粉丝私信来问一个问题，同意贴上来，但不让放图，所以手写一遍贴上来。

Given a positive integer N, compute the following sum:
When N is odd:
$$N^2?(N?1{)}^2+(N?2{)}^2?(N?3{)}^2+\dots +3^2?2^2+1^2$$
When N is even:
$$N^2?(N?1{)}^2+(N?2{)}^2?(N?3{)}^2+\dots ?3^2+2^2?1^2$$

where $$4\le N\le 10^{18}.$$

1.Recursive Sum in Erlang

1. Write a recursive function practical8_id:sum(N) to compute the sum of small numbers (between 4 and 4000).

2. Ask yourself whether it is better to implement this recursive program in Java or Erlang.
   Try to justify your reasoning with at least three points.

2.Efficient Sum in Erlang

1. Write a function practical8_id:efficient(N) to efficiently compute the sum of
   large numbers(between 4 and 10^18).
2. Compare the outputs of the efficient Erlang program with the outputs of the efficient Java program. Are they equal? Which solution is more elegant?

1.公式中间的… 是like的意思，我之前还以为是and意思，得分成两段做。这题不太严谨。
2. 偶数的公式前面缺减号，不太严谨。（和粉丝沟通过）应该为：
$$?N^2?(N?1{)}^2+(N?2{)}^2?(N?3{)}^2+\dots ?3^2+2^2?1^2$$

挺有意思的一道开放性问题。整体来说比较简单，leetcode的入门难度。

整个题目的翻译

1.在Erlang中使用递归方法

1. 写一个递归函数practical8_id:sum(N)来计算求和，N为小数字(4到4000之间)。
2. 问问自己用Java还是Erlang实现这个递归程序更好。
   试着用至少三点来证明你的推理。

2.效率更高的Erlang Sum

1. 写一个函数practical8_id:efficient(N)来高效地计算和，N为较大的数字(在4到10^18之间)。
2. 比较高效Erlang程序的输出与高效Java程序的输出。他们是平等吗?哪个解决方案更优雅?

个人认为：效率更高，应该是诱导你使用尾递归

java程序

package partical8_ap114;

public class partical8_ap114 {
	public static void main(String [] args) {
		
	}

	public static int sum(int x,int flag){
		if(x == 0) return 0;
		return sum(x-1,flag*-1) + x*x*flag;
	}
	public static int efficient(int x,int sum, int flag){
		if(x == 0) return sum;
		return efficient(x-1,sum+x*x*flag,flag*-1);
	}
	
}

erl程序

%%	题目:给一个整数N求返回结果
%%	当N为奇数时：
%%		N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... + 3^2 - 2^2 + 1^2
%%	当N为偶数时：
%%		-N^2 - (N-1)^2 + (N-2)^2 - (N-3)^2 + ... - 3^2 + 2^2 - 1^2
%%	N取值范围4 <= N <= 10^18
-module(partical8_ap114).
-export([sum/1, test_sum/0, efficient/1]).

%% 1：使用递归Sum计算结果
%% 1.1 N范围[4,4000],写个能计算结果的递归程序
sum(N) when N >=4 andalso N =< 4000 ->
	case N rem 2 of
		0 -> %% this is even number.
			sum_(N,-1);
		_ -> %% this is odd number.
			sum_(N,1)
	end.

sum_(0, _) -> 0;
sum_(N, Flag) ->
	sum_(N-1, Flag * -1) + N * N * Flag.


%% test方法:运行此方法返回全为true即可证明sum方法正确
test_sum() ->
%% 手算推导：
%% when n=4:
%% sum=-16+9-4+1=-10
%% when n=5:
%% sum=25-16+9-4+1=15
%% when n=6:
%% sum=-36+25-16+9-4+1=-21
	{
		-10 =:= sum(4),
		15 =:= sum(5),
		-21 =:= sum(6)
	}.

%% 1.2 问问自己用Java还是Erlang实现这个递归程序更好,试着用至少三点来证明你的推理。
%% 我认为这个递归程序,使用Erlang比Java更好. 
%% 题目中的better,我个人理解的不仅仅是程序的运行效率,还有易读,易维护,可靠性,鲁棒性
%% VP1:显然,Erlang的语法就决定了其代码易读,小巧的优点.
%% VP2:Erlang是一门函数式语言,特别是对计算题目中的数学表达式非常合适.因为它天生就是以数学角度看待问题.
%% VP3:Erlang更加灵活


%% 2: 使用效率更高的Sum计算结果
%% 2.1
%% 更有效率的sum方法,tail recursive 
efficient(N) when N >=4 andalso N =< 4000 ->
	case N rem 2 of
		0 -> %% this is even number.
			efficient(N,0,-1);
		_ -> %% this is odd number.
			efficient(N,0,1)
	end.

efficient(0, Sum, _) -> Sum;
efficient(N, Sum, Flag) ->
	efficient(N-1, Sum + N * N * Flag, Flag * -1).

%% 2.2 比较高效Erlang程序的输出与高效java程序的输出。
%% 他们是平等的吗?哪个解决方案更优雅?
%% 毫无疑问,输出相等.
%% （留给读者回答）

开放性问题，无标准答案，如果你有更好的答案欢迎一起讨论。

阅读世界，共赴山海

423全民读书节，邀你共读