b**a
发帖数: 51 | 1 家庭作业，要求用CDR 和 CAR 递归求一个非空数组的Median，巨多限制，具体如下，
请大牛帮忙，多谢。
Write a function median in Scheme that takes a nonempty list L of positive
integers (zero is not considered a positive integer) and other auxiliary
parameters of your choice. The list L is flat (i.e., it does not contain
sublists) and it is sorted in ascending order. If the length of list L is
odd, the function median returns the median element in the list, i. e. , the
middle number that divides the list into two halves of equal length so that
the median is greater or equal to all numbers preceding it, and lower or
equal to all numbers succeeding it. If the length of L is even, the function
median returns 0. It is up to you to choose the auxiliary parameters that
median takes. All auxiliary parameters must be numeric (not lists) and
should have initial values set to zero. For example, if L is ‘(1 2 3) and
you decide to use two additional auxiliary parameters, median should be
called as follows:
(median ‘(1 2 3) 0 0)
If there are three auxiliary parameters, then it must be called:
(median ‘( 1 2 3) 0 0 0 ) and so on.
Examples (for the sake of simplicity the auxiliary parameters are omitted;
in the actual calls they need to be set to zeros and placed right after the
list):
(median ‘(1)) returns 1
(median ‘(1 2)) returns 0
(median ‘(1 2 3)) returns 2
(median ‘( 1 2 3 4) returns 0
(median ‘( 3 3 3)) returns 3
(median ‘(1 4 7 10 11)) returns 7
(median ‘(2 4 4 10 10)) returns 4
(median ‘(10 13 14 15 20 20 40)) returns 15
(median ‘(20 24 25 31 45 56 70 80)) returns 0
(median ‘(15 22 25 30 36 42 48 60 70)) returns 36
The whole solution must be packed in one recursive function median which
must look as follows:
(define median (lambda (
initially set to zero>)
(cond
...
)))
In other words, you have to choose your auxiliary parameters and define a
COND statement.
Inside COND, you can use ONLY the following constructs:
- null?
- car
- cdr
- else
- =
- +
- median
- cond
- if
- user defined names (for your variables)
- integer literals
- parentheses
You cannot use a construct if it is not listed above. The use of built-in
functions is not allowed. You cannot define or call any other function with
the exception of median. In other words, your code must use only one
function, median, which must be defined using the constructs from the list
above. | m*****n
发帖数: 204 | 2 So your problem is you can't call built in functions?
You can call recursively to find the length, and
Find the median during backtrack
the
that
function
【在 b**a 的大作中提到】
: 家庭作业，要求用CDR 和 CAR 递归求一个非空数组的Median，巨多限制，具体如下，
: 请大牛帮忙，多谢。
: Write a function median in Scheme that takes a nonempty list L of positive
: integers (zero is not considered a positive integer) and other auxiliary
: parameters of your choice. The list L is flat (i.e., it does not contain
: sublists) and it is sorted in ascending order. If the length of list L is
: odd, the function median returns the median element in the list, i. e. , the
: middle number that divides the list into two halves of equal length so that
: the median is greater or equal to all numbers preceding it, and lower or
: equal to all numbers succeeding it. If the length of L is even, the function
| b**a
发帖数: 51 | 3 Thanks for your tips. I can not use any built in function except those
provided in the description, CAR and CDR. I can use recursion to find the
length. Could you please tell me how to find the median during the backtrack
? Could you please provide some sample code? Your help would be greatly
appreciated. Homework is due tonight and very anxious now. | w******p
发帖数: 166 | 4 notice that "it is sorted in ascending order" -- you just need one
additional parameter to count where you are in the stepping, something like | s******d
发帖数: 363 | 5 a nonempty list L of positive integers (zero is not considered a positive
integer)
负值不在原来的list里，所以可以利用负的返回值来传递一点信息吧 | w******p
发帖数: 166 | 6 go idea solnoid, this works with racket:
; m: counting length
; n: counting half of length
; p: n*2
; o: odd or even position
(define median
(lambda (xs m n p o)
(if (null? xs)
(if (= m p)
0
(- 0 n))
(let ((cb (median (cdr xs) (+ m 1)
(if (= o 0) (+ n 1) n)
(if (= o 1) (+ p 2) p)
(if (= o 0) 1 0))))
(if (= (- -1 m) cb)
(car xs)
cb)))))
> (median '(4 5 6) 0 0 0 0)
5
> (median '(4) 0 0 0 0)
4
> (median '(4 5 6 7 8) 0 0 0 0)
6
> (median '(4 5) 0 0 0 0)
0
> (median '(4 5 6 7) 0 0 0 0)
0
> (median '() 0 0 0 0)
0 |
|
