Homework Exercises 1

第一题

返回所有这样的整数k的和：

• 1 <= k < N
• N可被k整除

/* 1a. */
/** Returns the sum of all integers, k, such that 1 <= k < N and
*  N is evenly divisible by k. */
static int factorSum(int N) {
// Fill in here
}

static int factorSum(int N) {
int i = 0;
int j = 0;
for (; i <= N / 2; i++) {
if (N % i == 0) {
j += i;
}
}
return j;
}

注意无需遍历N，只需要到N/2就行了。

打印出0 - N间的所有相亲数，每一对占一行，小的在前，大的在后。

所谓想亲数就是：指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。

例如220与284：

• 220的全部约数(除掉本身)相加是：1+2+4+5+10+11+20+22+44+55+110=284
• 284的全部约数(除掉284本身)相加的和是：1+2+4+71+142=220

/* 1b. */
/** Print the set of all sociable pairs whose members are all
*  between 1 and N>=0 (inclusive) on the standard output (one pair per
*  line, smallest member of each pair first, with no repetitions). */
static void printSociablePairs(int N) {
// Fill in here
}

static void printSociablePairs(int N) {
int i = 0;
int j = 0;
for(; i<=N; i++){
j = factorSum(i)
if (j > i){
system.out.println(i + ", " + j);
}
}
}

 

第二题

根据下面的简单链表实现完成下面题目。

import java.util.Formatter;
/** Scheme-like pairs that can be used to form a list of integers.
*  @author P. N. Hilfinger
*  [Do not modify this file.]
*/
public class IntList {
/** First element of list. */
public int head;
/** Remaining elements of list. */
public IntList tail;
/** A List with head HEAD0 and tail TAIL0. */
public IntList(int head0, IntList tail0) {
head = head0;
tail = tail0;
}
/** A List with null tail, and head = 0. */
public IntList() {
/* NOTE: public IntList () { }  would also work. */
this (0, null);
}
/** Returns a new IntList containing the ints in ARGS. */
public static IntList list(Integer ... args) {
IntList result, p;
if (args.length > 0) {
result = new IntList(args[0], null);
} else {
return null;
}
int k;
for (k = 1, p = result; k < args.length; k += 1, p = p.tail) {
p.tail = new IntList(args[k], null);
}
return result;
}
/** Returns true iff X is an IntList containing the same sequence of ints
*  as THIS. */
public boolean equals(Object x) {
if (!(x instanceof IntList)) {
return false;
}
IntList L = (IntList) x;
IntList p;
for (p = this; p != null && L != null; p = p.tail, L = L.tail) {
if (p.head != L.head) {
return false;
}
}
if (p != null || L != null) {
return false;
}
return true;
}
@Override
public int hashCode() {
return head;
}
@Override
public String toString() {
Formatter out = new Formatter();
String sep;
sep = "(";
for (IntList p = this; p != null; p = p.tail) {
out.format("%s%d", sep, p.head);
sep = ", ";
}
out.format(")");
return out.toString();
}
}

返回一个IntList包含IntList A，后面跟着IntList B，不允许使用new。

/* 2a. */
/** Returns a list consisting of the elements of A followed by the
*  elements of B.  May modify items of A. Don't use 'new'. */
static IntList dcatenate(IntList A, IntList B) {
// Fill in here
}

static IntList dcatenate(IntList A, IntList B) {
IntList p
for (p = A; p != null; p = p.tail;){
if(p.tail == null){
p.tail = B;
}
}
return A;
}

注意链表的概念。

返回一个IntList的一部分，从原IntList L的第start个元素开始，长度为len。不允许改变原IntList的每个元素，如果元素不存在会抛出错误。

/* 2b. */
/** Returns the sublist consisting of LEN items from list L,
*  beginning with item #START (where the first item is #0).
*  Does not modify the original list elements.
*  It is an error if the desired items don't exist. */
static IntList sublist(IntList L, int start, int len) {
//Fill in here
}

static IntList sublist(IntList L, int start, int len) {
IntList p;
IntList k;
IntList j;
int i = 0;
int head0;
for (p = L; i < start + len; p = p.tail, i++){
if (i == start){
head0 = p.head;
k = new IntList(head0, null);
j = k;
} else if (i > start && i < start + len)
head0 = p.head;
j.tail = new IntList(head0, null);
j = j.tail;
}
}
return k;
}

返回一个IntList的一部分，从原IntList L的第start个元素开始，长度为len。需要改变原IntList的元素，如果元素不存在会抛出错误。

/* 2c. */
/** Returns the sublist consisting of LEN items from list L,
*  beginning with item #START (where the first item is #0).
*  May modify the original list elements. Don't use 'new'.
*  It is an error if the desired items don't exist. */
static IntList dsublist(IntList L, int start, int len) {
// Fill in here
}

static IntList dsublist(IntList L, int start, int len) {
IntList p;
int i = 0;
for (p = L; i <= start + len; p = p.tail, i++){
if (i == start){
L = p;
} else if (i == start + len){
p = null;
}
}
return L;
}

 

 

分类: Date Structures, Java

标签: Java, Date Structures