Redian新闻
>
出个题,怎么把这段过程式代码转换成函数式
avatar
出个题,怎么把这段过程式代码转换成函数式# Programming - 葵花宝典
w*f
1
律师给LD(主申请人)表上填的A#就是LD的140批准后写的号码,而给我填的是我以前
申请过OPT的卡上边的。这个A#是谁给分配的,放在哪个系统里?感觉挺混乱的一个东
西,根据前边考古的帖子,好像如果不填这个号码,移民局就会给再随便分配一个。
avatar
l*s
2
看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
用都是搬运/转化数据,不会有这种要求 :-)
5
13 14 15 16 1
12 23 24 17 2
11 22 25 18 3
10 21 20 19 4
9 8 7 6 5
int a[MAXN][MAXN];
int main() {
int n, x, y, tot = 0;
scanf("%d", &n);
memset(a, 0, sizeof(a));
tot = a[x=0][y=n-1] = 1;
while(tot < n* n) {
while(x+1 < n && !a[x+1][y]) a[++x][y] = ++tot;
while(y-1 >= 0 && !a[x][y-1]) a[x][--y] = ++tot;
while(x-1 >= 0 && !a[x-1][y]) a[--x][y] = ++tot;
while(y+1 < n && !a[x][y+1]) a[x][++y] = ++tot;
}
for (x = 0; x < n; ++x) {
for (y = 0; y < n; y++)
printf("%3d", a[x][y]);
printf("n");
}
}
avatar
N*g
3
副申请人如果从来没有这个号,就是分配一个。但是将来这就是副申请人的号码了,会
出现在绿卡上。
avatar
d*a
4
tot = a[x=0][y=n-1] = 1;
这样的代码,放现在过不了review吧,呵呵。
avatar
w*f
5
以前好像填别的什么表格的时候,提到过A#,当时觉得自己没有,就空着。现在才知道
OPT时候申请的EAD卡上有这个号码。

【在 N********g 的大作中提到】
: 副申请人如果从来没有这个号,就是分配一个。但是将来这就是副申请人的号码了,会
: 出现在绿卡上。

avatar
h*i
6
What's the name of this thing?
Normally, you don't directly translate code from IP to FP.
You implement the algorithm as appeared in paper, book, or whatever
publication.
Normally, the algorithm described in publications is very short, with pseudo
code that is very easy to translate into FP code.

【在 l*********s 的大作中提到】
: 看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
: 用都是搬运/转化数据,不会有这种要求 :-)
: 5
: 13 14 15 16 1
: 12 23 24 17 2
: 11 22 25 18 3
: 10 21 20 19 4
: 9 8 7 6 5
: int a[MAXN][MAXN];
: int main() {

avatar
v*g
7
我汗。。。 不是说空着吗????
avatar
l*s
8
没啥歧义,why not?

【在 d***a 的大作中提到】
: tot = a[x=0][y=n-1] = 1;
: 这样的代码,放现在过不了review吧,呵呵。

avatar
a*x
9
无所谓

【在 v****g 的大作中提到】
: 我汗。。。 不是说空着吗????
avatar
l*s
10
没名字,就是个讲c语法中变量++运算符的例题,要求是按螺旋线填充二维数组。

pseudo

【在 h*i 的大作中提到】
: What's the name of this thing?
: Normally, you don't directly translate code from IP to FP.
: You implement the algorithm as appeared in paper, book, or whatever
: publication.
: Normally, the algorithm described in publications is very short, with pseudo
: code that is very easy to translate into FP code.

avatar
d*c
11
随便说说,懒得去真的写代码,因为反正你也是随便找段代码
要改变编程风格,就不可能“转换”或者“翻译”,那肯定觉得别扭。这段代码本身设
计就是过程式的,要改就得从根子上改。
所谓螺旋,就是一圈一圈地赋值。对一个大小为n的矩阵外圈四条边坐标规律是可以抽
象成函数的
,给个起始值i,矩阵大小n,返回按顺序的坐标对。
i: (1, n) 我这里用1-index,好写一点
i+1: (2, n)
...
i+n: (n, n-1)
i+n+1: (n, n-2)
...
写好这个函数,然后逐次调用就是了。可以在每次调用之后就给这些坐标赋值,也可以
全写好了最后赋值。
这样抽象的外圈赋值函数定义是更简单,更容易测试的吧?

【在 l*********s 的大作中提到】
: 看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
: 用都是搬运/转化数据,不会有这种要求 :-)
: 5
: 13 14 15 16 1
: 12 23 24 17 2
: 11 22 25 18 3
: 10 21 20 19 4
: 9 8 7 6 5
: int a[MAXN][MAXN];
: int main() {

avatar
n*p
12
这道题和IP还是FP没什么关系啊。
就是find 1到n^2的对应matrix坐标。这个很容易定义,比如在什么情况下坐标上,下
,左,右移动。过完一便所有数字都有相应的matrix坐标。
avatar
l*s
13
Agree. However, given the requirement, coming up with procedural coding is
fairly easy for most programmers, but not so trivial in FP, right? My gut
feeling is that expressing the rules would not be nearly as neat as C.

【在 d******c 的大作中提到】
: 随便说说,懒得去真的写代码,因为反正你也是随便找段代码
: 要改变编程风格,就不可能“转换”或者“翻译”,那肯定觉得别扭。这段代码本身设
: 计就是过程式的,要改就得从根子上改。
: 所谓螺旋,就是一圈一圈地赋值。对一个大小为n的矩阵外圈四条边坐标规律是可以抽
: 象成函数的
: ,给个起始值i,矩阵大小n,返回按顺序的坐标对。
: i: (1, n) 我这里用1-index,好写一点
: i+1: (2, n)
: ...
: i+n: (n, n-1)

avatar
l*s
14
Aren't you describing the posted IP coding? I believe to accomplish this in
FP you need to have different mindset.

【在 n***p 的大作中提到】
: 这道题和IP还是FP没什么关系啊。
: 就是find 1到n^2的对应matrix坐标。这个很容易定义,比如在什么情况下坐标上,下
: ,左,右移动。过完一便所有数字都有相应的matrix坐标。

avatar
d*c
15
过程思维是自然的,因为大家学的时候就是这样学的。问题的描述让人也容易用过程思
维去解决。
思维模式转变过后,这个外圈函数写起来也不难,读起来也容易。
“大多数人写起来不习惯”不是方法真正的缺点或者优点。
另外我不觉得原来那个过程代码“neat”。如果某个地方符号错了或者偏差了一位,一
眼是不容易看出来的。如果有什么边界情况,更不好说。
如果问题再复杂一点,在你移动的同事还要做什么事情,那就更复杂而且容易出错了。
我是觉得循环内的代码越复杂,越需要在大脑中维护状态,那个很累。尽量把循环内做
的事情足够简单,是件好事。

【在 l*********s 的大作中提到】
: Agree. However, given the requirement, coming up with procedural coding is
: fairly easy for most programmers, but not so trivial in FP, right? My gut
: feeling is that expressing the rules would not be nearly as neat as C.

avatar
l*s
16
you write one let me see see then?

【在 d******c 的大作中提到】
: 过程思维是自然的,因为大家学的时候就是这样学的。问题的描述让人也容易用过程思
: 维去解决。
: 思维模式转变过后,这个外圈函数写起来也不难,读起来也容易。
: “大多数人写起来不习惯”不是方法真正的缺点或者优点。
: 另外我不觉得原来那个过程代码“neat”。如果某个地方符号错了或者偏差了一位,一
: 眼是不容易看出来的。如果有什么边界情况,更不好说。
: 如果问题再复杂一点,在你移动的同事还要做什么事情,那就更复杂而且容易出错了。
: 我是觉得循环内的代码越复杂,越需要在大脑中维护状态,那个很累。尽量把循环内做
: 的事情足够简单,是件好事。

avatar
d*c
17
用python写一下坐标:
n = 5
# each edge start from first, stop before the last, which is the start of
next edge
edge_1 = (range(n-1), [n-1] * (n-1))
edge_4 = ([0] * (n-1), range(n-1))
edge_2 = ([n-1] * (n-1), range(n-1, 0, -1))
edge_3 = (range(n-1, 0, -1), [0] * (n-1))
# edge_1 to edge_4:
([0, 1, 2, 3], [4, 4, 4, 4])
([4, 4, 4, 4], [4, 3, 2, 1])
([4, 3, 2, 1], [0, 0, 0, 0])
([0, 0, 0, 0], [0, 1, 2, 3])
用了python2因为用3的话range还得转换成list才好打印,有点麻烦
每条边是从头到尾,不包括最后一个
四条边写的时候把1和4写在一起,因为坐标是对称的,比较容易比较。这种代码的边界
和0-index/1-index特别容易出错,对称写容易比较。
写边的时候分别写x和y比较容易,写完了再写个函数把每条边的(list of x, list of
y)转换成[(x1,y1), (x2,y2)...] 的坐标对形式。这个转换函数简单到不能再简单了吧。
把四条边的坐标对按顺序连起来,按从1到n赋值。这个过程也足够简单吧。
所以过程式写法的一个大循环拆成了
1. 写四条边的函数
2. 把边的坐标list转成坐标对
3. 1-2 处理了一圈,调用他们处理每一圈
4. 赋值。可以在最后赋值,或者在第三步赋值。
avatar
d*c
18
要比较的话,函数式写法代码可能要长一点,长的不多。
过程式里很多边界条件检查,函数式里定义了“边”之后是比较容易写的(0-index和1
-index不能混着用,否则容易出错)。其他几个helper函数简单到不可能出错。
最重要的区别就是过程式一边走一边改,函数式分成好几步,每一步完成一个小目标,
最后再一起改。这样空间消耗肯定更多,如果是嵌入式编程,或者内存不够,会比较困
难。不过只要空间够,对程序员是友好的,尤其是当你半年后发现需要做点修改的时候。
avatar
l*s
19
I think your code has bug as inner loop needs to adjust offset /bounds
accordingly. Also, pairing 1,4 and 2,3 is probably not a good idea
as it breaks homogeneity.
But although it is more verbose, I can see how generally you tackle the
problems in FP, thanks a lot!

【在 d******c 的大作中提到】
: 用python写一下坐标:
: n = 5
: # each edge start from first, stop before the last, which is the start of
: next edge
: edge_1 = (range(n-1), [n-1] * (n-1))
: edge_4 = ([0] * (n-1), range(n-1))
: edge_2 = ([n-1] * (n-1), range(n-1, 0, -1))
: edge_3 = (range(n-1, 0, -1), [0] * (n-1))
: # edge_1 to edge_4:
: ([0, 1, 2, 3], [4, 4, 4, 4])

avatar
d*c
20
1/4, 2/3写的好处是变量部分xy对调一下,常量部分一个是头一个是尾。1234写的好处
是每一个的尾和下一个头是一样的,也有好处。无所谓对错吧,个人喜好。
这个函数只处理一圈,下一内圈再调用这个函数,但是用新的起始值,n-2作为矩阵大
小。offset/bounds没有什么需要调整的。
get_coordinates(0, 5) #可以返回总共有多少个点,这里是16
get_coordinates(17, 3) #通过上个函数的返回值确定起始值
get_coordinates(25, 1)

【在 l*********s 的大作中提到】
: I think your code has bug as inner loop needs to adjust offset /bounds
: accordingly. Also, pairing 1,4 and 2,3 is probably not a good idea
: as it breaks homogeneity.
: But although it is more verbose, I can see how generally you tackle the
: problems in FP, thanks a lot!

avatar
h*i
21
(ns test.spiral)
(defn transpose [m]
(when (seq m)
(apply mapv vector m)))
(defn rotate [m]
(-> m transpose reverse))
(defn spiral [m]
(when (seq m)
(concat (first m)
(-> m rest rotate spiral))))
(defn seq->matrix [s n]
(->> (partition n s)
(mapv vec)
vec))
(defn spiral-matrix [n]
(let [base (range 1 (inc (* n n)))
order (spiral (seq->matrix base n))
order' (map (zipmap order base) base)]
(seq->matrix order' n)))

【在 l*********s 的大作中提到】
: 看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
: 用都是搬运/转化数据,不会有这种要求 :-)
: 5
: 13 14 15 16 1
: 12 23 24 17 2
: 11 22 25 18 3
: 10 21 20 19 4
: 9 8 7 6 5
: int a[MAXN][MAXN];
: int main() {

avatar
n*p
22
great solution! to match exactly what he previously posted result:
(into [] (map reverse (transpose (spiral-matrix 5))))
=> [(13 14 15 16 1) (12 23 24 17 2) (11 22 25 18 3) (10 21 20 19 4) (9 8 7 6
5)]

【在 h*i 的大作中提到】
: (ns test.spiral)
: (defn transpose [m]
: (when (seq m)
: (apply mapv vector m)))
: (defn rotate [m]
: (-> m transpose reverse))
: (defn spiral [m]
: (when (seq m)
: (concat (first m)
: (-> m rest rotate spiral))))

avatar
h*i
23
这个题FP与IP的思维方式区别还是明显的,FP是对数据整体进行一步步简单变换,IP是
对单个数据进行复杂变换。

【在 l*********s 的大作中提到】
: 看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
: 用都是搬运/转化数据,不会有这种要求 :-)
: 5
: 13 14 15 16 1
: 12 23 24 17 2
: 11 22 25 18 3
: 10 21 20 19 4
: 9 8 7 6 5
: int a[MAXN][MAXN];
: int main() {

avatar
n*p
24
(defn seq->matrix [s n]
(->> (partition n s)
(mapv vec)
vec)) ;; this vec looks unnecessary?

【在 h*i 的大作中提到】
: 这个题FP与IP的思维方式区别还是明显的,FP是对数据整体进行一步步简单变换,IP是
: 对单个数据进行复杂变换。

avatar
h*i
25
Correct, it's not necessary. (mapv vec) is not necessary either.
Just used to make the results look nicer during testing.
In fact the whole thing could be written in a single function if we don't
care about readability.
(defn spiral-matrix-fn [n]
(let [base (range 1 (inc (* n n)))
transpose #(when (seq %) (apply mapv vector %))
rotate #(-> % transpose reverse)]
(letfn [(spiral [m]
(when (seq m)
(concat (first m) (-> m rest rotate spiral))))]
(->> base
(map (zipmap (spiral (rotate (partition n base))) base))
(partition n)))))
still pretty readable.

【在 n***p 的大作中提到】
: (defn seq->matrix [s n]
: (->> (partition n s)
: (mapv vec)
: vec)) ;; this vec looks unnecessary?

avatar
n*p
26
nicely done!

【在 h*i 的大作中提到】
: Correct, it's not necessary. (mapv vec) is not necessary either.
: Just used to make the results look nicer during testing.
: In fact the whole thing could be written in a single function if we don't
: care about readability.
: (defn spiral-matrix-fn [n]
: (let [base (range 1 (inc (* n n)))
: transpose #(when (seq %) (apply mapv vector %))
: rotate #(-> % transpose reverse)]
: (letfn [(spiral [m]
: (when (seq m)

avatar
w*g
27
同意。fp方法往往有完全不同的思路。直接翻译对fp不公。

:随便说说,懒得去真的写代码,因为反正你也是随便找段代码
avatar
l*s
28
大牛 ...,不明覺厲 :-)

【在 h*i 的大作中提到】
: Correct, it's not necessary. (mapv vec) is not necessary either.
: Just used to make the results look nicer during testing.
: In fact the whole thing could be written in a single function if we don't
: care about readability.
: (defn spiral-matrix-fn [n]
: (let [base (range 1 (inc (* n n)))
: transpose #(when (seq %) (apply mapv vector %))
: rotate #(-> % transpose reverse)]
: (letfn [(spiral [m]
: (when (seq m)

avatar
T*x
29
楼主的写法看来已经是极简了。我用python递归写了一下,比楼主的还长。递归是个尾
递归,跟循环差不多。python需要格式,copy paste不行,所以贴个图。
[在 littlebirds (dreamer) 的大作中提到:]
:看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
:用都是搬运/转化数据,不会有这种要求 :-)
:int a[MAXN][MAXN];
:int main() {
: int n, x, y, tot = 0;
: scanf("%d", &n);
: memset(a, 0, sizeof(a));
: tot = a[x=0][y=n-1] = 1;
: while(tot < n* n) {
: while(x+1 < n && !a[x+1][y]) a[++x][y] = ++tot;
:..........
avatar
j*v
30
这个比hci写的要差点,他那个code几乎就是把算法过程叙述一遍,简单明了。

【在 T*******x 的大作中提到】
: 楼主的写法看来已经是极简了。我用python递归写了一下,比楼主的还长。递归是个尾
: 递归,跟循环差不多。python需要格式,copy paste不行,所以贴个图。
: [在 littlebirds (dreamer) 的大作中提到:]
: :看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
: :用都是搬运/转化数据,不会有这种要求 :-)
: :int a[MAXN][MAXN];
: :int main() {
: : int n, x, y, tot = 0;
: : scanf("%d", &n);
: : memset(a, 0, sizeof(a));

avatar
T*x
31
他那个算法本身我没有理解,spiral把我转糊涂了。

【在 j*****v 的大作中提到】
: 这个比hci写的要差点,他那个code几乎就是把算法过程叙述一遍,简单明了。
avatar
j*v
32
那个函数就是顺时针从外到里把数排列一遍而已

【在 T*******x 的大作中提到】
: 他那个算法本身我没有理解,spiral把我转糊涂了。
avatar
T*x
33
嗯。不错。最后那个映射也挺绕头的:1,从右上角把矩阵数字顺时针从外向里排列一
遍,2,把这串数字和1到25顺序排列的数字映射一下,3,把映射的结果数字按照映射
的自变量数字排列一下,再按矩阵格式排列,就得到最终结果。最后这步也挺绕头的。
- 我是说code很简洁,但是概念上还是有点绕头的。
不错。我又复习了一遍Clojure。- 学过一点,但是基本没用过。

【在 j*****v 的大作中提到】
: 那个函数就是顺时针从外到里把数排列一遍而已
avatar
T*x
34
用python翻译了一下这个算法。python没有partition和zipmap函数,自己写了一下。
python没有Clojue 的 thread-first, thread-last,直接用函数composition。为避免
缩进全部写成一行的函数。
####
d = 5
base = [ i+1 for i in range(d*d)]
partition = lambda n: lambda s: [[s[i+j*n] for i in range(n)] for j in range
(len(s)//n)]
zipmap = lambda s1, s2: lambda n: dict(zip(s1, s2))[n]
transpose = lambda m: [list(item) for item in zip(*m)]
rotate = lambda m: list(reversed(transpose(m)))
def spiral(m): return [] if len(m) == 0 else (m[0] + spiral(rotate(m[1:])))
result = partition(d)(list(map(zipmap(spiral(rotate(partition(d)(base))),
base), base)))
def printGrid(grid): [print(grid[i]) for i in range(d)]
printGrid(result)
####
玩一下。其实这个算法从思维的直接性来说,不如过程式那个算法。直到现在我也没有
完全想清楚最后那个螺旋排列能得到正确的结果,当然验证通过之后我就不费那个劲了。

【在 h*i 的大作中提到】
: Correct, it's not necessary. (mapv vec) is not necessary either.
: Just used to make the results look nicer during testing.
: In fact the whole thing could be written in a single function if we don't
: care about readability.
: (defn spiral-matrix-fn [n]
: (let [base (range 1 (inc (* n n)))
: transpose #(when (seq %) (apply mapv vector %))
: rotate #(-> % transpose reverse)]
: (letfn [(spiral [m]
: (when (seq m)

avatar
l*s
35
是的,函数式编程写的好看,但是要达到这样的效果需要的思考过程却是很烧脑的,
要不为啥公认写haskell的就是牛B呢。

【在 T*******x 的大作中提到】
: 嗯。不错。最后那个映射也挺绕头的:1,从右上角把矩阵数字顺时针从外向里排列一
: 遍,2,把这串数字和1到25顺序排列的数字映射一下,3,把映射的结果数字按照映射
: 的自变量数字排列一下,再按矩阵格式排列,就得到最终结果。最后这步也挺绕头的。
: - 我是说code很简洁,但是概念上还是有点绕头的。
: 不错。我又复习了一遍Clojure。- 学过一点,但是基本没用过。

avatar
k*i
36
import Data.List
square n i = map ((p,q) -> zip p q) [(a,b),(b,c),(c,d),(d,a)]
where x = n-i+1; y = x-i+1
a = [i..x]; b = replicate y x; c = reverse a; d = replicate y i
spiral n = map (map snd)
. groupBy (((x,_),_) ((y,_),_) -> x == y)
. sort
$ zip c [1..n*n]
where c = nub
. foldl1 (++)
. foldl1 (++)
$ map (square n) [1..b]
b | even n = a | otherwise = a+1 where a = n`div`2
main = do
print $ spiral 5
-- [[13,14,15,16,1],[12,23,24,17,2],[11,22,25,18,3],[10,21,20,19,4],[9,8,7
,6,5]]
print $ spiral 4
-- [[10,11,12,1],[9,16,13,2],[8,15,14,3],[7,6,5,4]]

【在 l*********s 的大作中提到】
: 看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
: 用都是搬运/转化数据,不会有这种要求 :-)
: 5
: 13 14 15 16 1
: 12 23 24 17 2
: 11 22 25 18 3
: 10 21 20 19 4
: 9 8 7 6 5
: int a[MAXN][MAXN];
: int main() {

avatar
l*s
37
WoW, Haskell!

【在 k****i 的大作中提到】
: import Data.List
: square n i = map ((p,q) -> zip p q) [(a,b),(b,c),(c,d),(d,a)]
: where x = n-i+1; y = x-i+1
: a = [i..x]; b = replicate y x; c = reverse a; d = replicate y i
: spiral n = map (map snd)
: . groupBy (((x,_),_) ((y,_),_) -> x == y)
: . sort
: $ zip c [1..n*n]
: where c = nub
: . foldl1 (++)

avatar
T*x
38
Haskell那个我也看了。程序写的很清楚,算法上有不容易理解的地方。
这种写法相当于结果的呈现。
clojure那个写法介于过程式写法和Haskell这个之间。

【在 l*********s 的大作中提到】
: WoW, Haskell!
avatar
k*i
39
这样更易读,更FP。
import Data.List
point' n i e k
| e=='R' = (a,j) | e=='B' = (j,b) | e=='L' = (b,i) | e=='T' = (i,a)
where (j,a,b) = (n-i-1,i+k,j-k)
edge' n i e = map (point' n i e) [0..n-i*2-2]
square' n i
| i*2+1==n = [(a,a)]
| otherwise = concat $ map (edge' n i) ['R','B','L','T']
where a = n`div`2
spiral' n = concat $ map (square' n) [0..ceiling (fromIntegral n /2) -1]
pair' n = zip (spiral' n) [1..n*n]
mat' = map (map snd) . groupBy cond' . sort . pair'
where cond' ((a,_),_) ((b,_),_) = a==b
main = do
print $ mat' 5
-- [[13,14,15,16,1],[12,23,24,17,2],[11,22,25,18,3],[10,21,20,19,4],[9,8,7
,6,5]]
print $ mat' 4
-- [[10,11,12,1],[9,16,13,2],[8,15,14,3],[7,6,5,4]]
--}

【在 T*******x 的大作中提到】
: Haskell那个我也看了。程序写的很清楚,算法上有不容易理解的地方。
: 这种写法相当于结果的呈现。
: clojure那个写法介于过程式写法和Haskell这个之间。

avatar
T*x
40
这个版本有“沿着边行走”这个概念了,确实答案的正确性更容易看出来了。

【在 k****i 的大作中提到】
: 这样更易读,更FP。
: import Data.List
: point' n i e k
: | e=='R' = (a,j) | e=='B' = (j,b) | e=='L' = (b,i) | e=='T' = (i,a)
: where (j,a,b) = (n-i-1,i+k,j-k)
: edge' n i e = map (point' n i e) [0..n-i*2-2]
: square' n i
: | i*2+1==n = [(a,a)]
: | otherwise = concat $ map (edge' n i) ['R','B','L','T']
: where a = n`div`2

avatar
a*e
41
用递归的方法可以得到更简单的实现:
import Control.Monad.Trans.State.Lazy
square n | n == 0 = return [[]]
| otherwise = do
col row new n
sq square (n - 1)
return $ zipWith (+++) sq col +++ row
new n = state (\i -> ([i..(i+n-1)], i+n))
l +++ x = l ++ [x]
main n = mapM_ print $ evalState (square n) 1
运行结果:
[1 of 1] Compiling Spiral ( Spiral.hs, interpreted )
Ok, one module loaded.
*Spiral> main 5
[13,14,15,16,1]
[12,23,24,17,2]
[11,22,25,18,3]
[10,21,20,19,4]
[9,8,7,6,5]
基本的思路是先从结构出发,从边长 n-1 的方块,经过旋转和添加最右列和最下行,
可以得到边长 n 的方块。然后再注意一下数字生成的顺序,用 state monad 封装一下
即可得到答案。这个两步走的思路其实是对问题的核心进行了抽象,适度的抽象(
abstraction)和组合(composition)是 FP 程序设计的核心。
avatar
T*x
42
不错。不过state monad确实太高级了。递归函数再加一个参数不行吗?
我用python翻译了一下,基本上直译。
python3里面iterable变成list有点麻烦,应该有更好的写法。

【在 a*****e 的大作中提到】
: 用递归的方法可以得到更简单的实现:
: import Control.Monad.Trans.State.Lazy
: square n | n == 0 = return [[]]
: | otherwise = do
: col : row new n
: sq square (n - 1)
: return $ zipWith (+++) sq col +++ row
: new n = state (\i -> ([i..(i+n-1)], i+n))
: l +++ x = l ++ [x]

avatar
h*c
43
n 为圈数,圈k里到外
V = [1,8,16, 。。。(2k-1)^2-(2k-3)^2]
对于k>=2圈,最小在左上角值为 其右下值-V[k]
顺序放左下右上
FP不放屁,有算法才能重复。

【在 l*********s 的大作中提到】
: 看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
: 用都是搬运/转化数据,不会有这种要求 :-)
: 5
: 13 14 15 16 1
: 12 23 24 17 2
: 11 22 25 18 3
: 10 21 20 19 4
: 9 8 7 6 5
: int a[MAXN][MAXN];
: int main() {

avatar
T*x
44
改了一下,把+函数去掉了,用python自己的list comprehension。more pythonic。

【在 T*******x 的大作中提到】
: 不错。不过state monad确实太高级了。递归函数再加一个参数不行吗?
: 我用python翻译了一下,基本上直译。
: python3里面iterable变成list有点麻烦,应该有更好的写法。

avatar
T*x
45
既然如此,那reversed也不要了,more more pythonic。哈哈。

【在 T*******x 的大作中提到】
: 改了一下,把+函数去掉了,用python自己的list comprehension。more pythonic。
avatar
k*i
46
一样的算法,2D数组简洁递归螺旋,免除复杂边界设定处理。
import Data.List as List
import Data.List.Split
import Data.Map
rotate = reverse . transpose
spiral [] = []
spiral (order:m) = order ++ spiral (rotate m)
rotate' = transpose . reverse
mat n = rotate' $ chunksOf n order'
where base = [1..n*n]
order = spiral $ chunksOf n base
order' = elems . fromList $ zip order base
main = mapM_ print $ mat 5

【在 h*i 的大作中提到】
: (ns test.spiral)
: (defn transpose [m]
: (when (seq m)
: (apply mapv vector m)))
: (defn rotate [m]
: (-> m transpose reverse))
: (defn spiral [m]
: (when (seq m)
: (concat (first m)
: (-> m rest rotate spiral))))

avatar
h*c
47
刚看前十几个回贴觉得楼主及其附庸有可能是他/她自己带的研究生或者小弟,觉得可
定要高尚到quarternian,affineness, dual space 啥的。
后来看看原题,觉得可以不那么高深。
但看了最近的答案,这坑可能真是这么挖的GTM52哪个题,楼主刷到深处。
觉得可以急转弯一下。
真的是好坑,不搞个one liner 看来是不来秀得。
avatar
k*i
48
照抄,除了不用STM。
mat' = mat 1
where rotate = map reverse . reverse
l+++x = l++[x]
mat _ 0 = [[]]
mat t n = zipWith (+++) m col +++ row
where m = rotate $ mat (k+1) n'
col = [t..i]
row = reverse [j..k]
(n',i,j,k) = (n-1,t+n'-1,i+1,j+n')
main = mapM_ print $ mat' 5

【在 a*****e 的大作中提到】
: 用递归的方法可以得到更简单的实现:
: import Control.Monad.Trans.State.Lazy
: square n | n == 0 = return [[]]
: | otherwise = do
: col : row new n
: sq square (n - 1)
: return $ zipWith (+++) sq col +++ row
: new n = state (\i -> ([i..(i+n-1)], i+n))
: l +++ x = l ++ [x]

avatar
k*i
49
再抄。
import Data.Map
import Data.List.Split
spiral n e i j t m | totherwise = m
where (e',i',j',t')
| e=='R' = let i'=i+1 in if i'< n && notMember (i',j ) m then (e,i
',j ,t') else ('B',i,j,t)
| e=='B' = let j'=j-1 in if j'>=0 && notMember (i ,j') m then (e,i
,j',t') else ('L',i,j,t)
| e=='L' = let i'=i-1 in if i'>=0 && notMember (i',j ) m then (e,i
',j ,t') else ('T',i,j,t)
| e=='T' = let j'=j+1 in if j'< n && notMember (i ,j') m then (e,i
,j',t') else ('R',i,j,t)
where t' = t+1
mat n = chunksOf n . elems . spiral n 'R' i j t $ insert (i,j) t empty
where (i,j,t) = (0,n-1,1)
main = mapM_ print $ mat 5

【在 T*******x 的大作中提到】
: 楼主的写法看来已经是极简了。我用python递归写了一下,比楼主的还长。递归是个尾
: 递归,跟循环差不多。python需要格式,copy paste不行,所以贴个图。
: [在 littlebirds (dreamer) 的大作中提到:]
: :看看大牛们有啥简洁的实现方法不 ^__^ 。 纯好奇,没有批函数式的意思,一般写应
: :用都是搬运/转化数据,不会有这种要求 :-)
: :int a[MAXN][MAXN];
: :int main() {
: : int n, x, y, tot = 0;
: : scanf("%d", &n);
: : memset(a, 0, sizeof(a));

avatar
k*i
50
WOW
算法1 1楼 c 24楼 py 44楼 hs
算法2 16楼 clj 29楼 py 41楼 hs
算法3 34楼 hs
算法4 36楼 hs 40楼 py 43楼 hs
除C以外,其他都是FP实现。
avatar
h*c
51
我目不转睛的盯了几分钟,发现有点对称性,或者叫conjugating比较合适一些,
最外一圈是18
再里一圈是42
相差24
avatar
h*c
52
还是从里到外1 到 k 圈
第k 圈有 8(k-1) 个数,对称的两个元素加和为 8(k-1)+2
因为对称,i,j的关系符合直线运算,j= k i + b或者用矢量旋转然后位移
第k-1 圈有 8(k-2) 个数,对称的两个元素加和为 8(k-1) + 2 + 8(k-1) + 8
(k-2) = 24k - 8 - 8 + 2 - 16 = 24k - 30 (= 72 - 30 = 42 BINGO)
我们算过斜轴上的值
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。