传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1261|回复: 21
收起左侧

[CS61B_Spring 2015] Discussion2 - Diagramming, Iterative vs. Recursive

[复制链接] |试试Instant~ |关注本帖
hurricane_e 发表于 2015-5-28 04:10:16 | 显示全部楼层 |阅读模式

[其他]CS61B Data Structure #14 - 2015-05-25@Berkeley

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
本帖最后由 hurricane_e 于 2015-5-28 04:14 编辑

Rt~
 楼主| hurricane_e 发表于 2015-5-29 06:45:57 | 显示全部楼层
回复 支持 反对

使用道具 举报

baiery 发表于 2015-5-29 11:56:54 | 显示全部楼层
奇怪,为什么我无法贴图?不是选择附件吗?
回复 支持 反对

使用道具 举报

 楼主| hurricane_e 发表于 2015-5-29 12:11:32 | 显示全部楼层
baiery 发表于 2015-5-29 11:56
奇怪,为什么我无法贴图?不是选择附件吗?

我一般是通过 ”回复-->高级模式-->图片“ 里面贴图的 有时候要等一等
回复 支持 反对

使用道具 举报

baiery 发表于 2015-5-29 12:50:50 | 显示全部楼层
图片是第一题
//2 Squaring a List

/** Destructively squares each element of the given IntList L.
* Don’t use ’new’; modify the original IntList.
* Should be written iteratively. */
public static IntList SquareDestructive(IntList L) {
        while(L!=null){
                L.head = L.head * L.head;
                L = L.tail;
        }
}


/** Non-destructively squares each element of the given IntList L.
* Don’t modify the given IntList.
* Should be written recursively*/
public static IntList SquareNonDestructive(IntList L) {
        if (L == null){
                return null;
        }
        else{
                IntList N = new IntList(L.head * L.head, SquareNonDestructive(L.tail));
                return N;
        }
}

//Destructive, recursively
public static IntList SquareDestructiveRecursive(IntList L) {
        if (L == null){
                return null;
        }
        else{
                L.head = L.head * L.head;
                return SquareDestructiveRecursive(L.tail); //Not sure here, should I use "return"?
        }
}

//Non-destructive, iteratively
public static IntList SquareNonDestructiveIterative(IntList L) {
        IntList N = new IntList();
       
        while(L!=null){
                N.head = L.head * L.head;
                L = L.tail;
                N = N.tail;
        }
}


//3 Reversing Linked Lists
/** Takes in an IntList and non-destructively returns an IntList whose
elements have been reversed.*/
public static IntList reverseNonDestructive(IntList lst) {
        IntList N = new IntList();

        while(lst!=null){
                N = IntList(lst.head, N);
                lst = lst.tail;
        }
        return N;
}


/** Bonus for bosses: Write reverseDestructive, which takes in an IntList
and destructively returns the same IntList with reversed elements.
You should not use ’new’.*/
public static void reverseDestructive(IntList L) {

}

最后一题不会啊,求解答啊,想了半天!
另外SquareDestructiveRecursive这个方法里,不知道要不要return,求解答!
感觉自己太搓了,三道discussion竟然搞了一上午,崩溃。。
Screen Shot 2015-05-29 at 11.58.53 AM.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| hurricane_e 发表于 2015-5-29 12:59:30 | 显示全部楼层
baiery 发表于 2015-5-29 12:50
图片是第一题
//2 Squaring a List

最后那个bonus方法我也不会╮(╯﹏╰)╭
同样学弱 做了好久。。也不太确定自己到底会了没。。

慢慢来吧=。=
回复 支持 反对

使用道具 举报

baiery 发表于 2015-5-29 13:41:13 | 显示全部楼层
hurricane_e 发表于 2015-5-29 12:59
最后那个bonus方法我也不会╮(╯﹏╰)╭
同样学弱 做了好久。。也不太确定自己到底会了没。。

//Destructive, recursively
public static IntList SquareDestructiveRecursive(IntList L) {
        if (L == null){
                return null;
        }
        else{
                L.head = L.head * L.head;
                return SquareDestructiveRecursive(L.tail); //Not sure here, should I use "return"?
        }
}
你觉得这里要写return嘛?可以直接写 SquareDestructiveRecursive(L.tail);吗?

另外我看你的代码里,最后一题第一句是 IntList M = null; 不用先 IntList M = new IntList(); 然后再赋初值吗?我好多格式化的问题都没搞清楚
回复 支持 反对

使用道具 举报

go7going 发表于 2015-5-29 18:27:06 | 显示全部楼层
求lz给个61B的课程链接呗~
回复 支持 反对

使用道具 举报

 楼主| hurricane_e 发表于 2015-5-30 03:16:08 | 显示全部楼层
go7going 发表于 2015-5-29 18:27
求lz给个61B的课程链接呗~

http://www.1point3acres.com/bbs/thread-135059-1-1.html
都在主帖第一楼里~
回复 支持 反对

使用道具 举报

 楼主| hurricane_e 发表于 2015-5-30 03:23:22 | 显示全部楼层
baiery 发表于 2015-5-29 13:41
//Destructive, recursively
public static IntList SquareDestructiveRecursive(IntList L) {
        ...

你的code有一点点问题,我觉得应该是这样:
public static IntList squareDestructiveRecursive(IntList L) {
        if (L == null){
                return null;
        }
        return new IntList (L.head * L.head, squareDestructiveRecursive(L.tail));
}

另外那个IntList M = null 的我其实也不太确定,但是可以compile,所以应该是可以的吧
回复 支持 反对

使用道具 举报

baiery 发表于 2015-5-30 08:48:55 | 显示全部楼层
hurricane_e 发表于 2015-5-30 03:23
你的code有一点点问题,我觉得应该是这样:
public static IntList squareDestructiveRecursive(IntList ...

你是用sublime来compile和查错的嘛?我配置了一下环境,发现各种错误啊。。。而且也不能查语法错误,你是怎么弄的啊?
回复 支持 反对

使用道具 举报

baiery 发表于 2015-5-30 08:50:42 | 显示全部楼层
hurricane_e 发表于 2015-5-30 03:23
你的code有一点点问题,我觉得应该是这样:
public static IntList squareDestructiveRecursive(IntList ...

而且我不懂啊,为什么我的不行啊?我的里面也修改了L.head为平方值了啊,还是说我return的东西一定要是一个IntList类是吗?不可以return 方法?
回复 支持 反对

使用道具 举报

karte_polo 发表于 2015-6-2 20:14:19 | 显示全部楼层
自己写了个LINKEDLIST 勉勉强强能完成这个LAB吧

最后一个NonDestructive的逆转链表好奇怪- -我在METHOD里面DEBUG出来结果是正确的,跳回MAIN之后链表就变成一个长度只有一的链表了- - 求JAVA 大神指点

import java.util.*;

public class CS61B_LAB02 {
        public static class IntList{
                private class Node{
                        private int Data;
                        Node(int data){
                                this.Data = data;
                        }
                       
                }
                private Node Header;
                private IntList tail;
                public IntList(IntList L1,IntList L2){
                        L1.tail = L2;
                }
                public IntList(int d,IntList nl){
                        this.Header = new Node(d);
                        this.tail = nl;
                }
               
                public void print(){
                        IntList p = this;
                        System.out.println();
                        while (p!=null){
                                System.out.print(" "+p.Header.Data);
                                p = p.tail;
                        }
                       
                }
               
        }
// above is an awkward implementation of LinkedLists
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                //test code below
                IntList L = new IntList(4, null);
                L.print();
                L = new IntList(3, L);
                L.print();
                L = new IntList(2, L);
                L.print();
                L = new IntList(1, L);
                L.print();
                SquareDestructive(L);
                L.print();
                reverseDestructive(L);
                L.print();

        }
        public static IntList SquareDestructive(IntList L) {
                while (L != null){
                        L.Header.Data =L.Header.Data*L.Header.Data;
                        L = L.tail;
                }
                return L;
        }
        public static IntList SquareNonDestructive(IntList L) {
                if (L == null){
                        return L;
                }
                int d = L.Header.Data;
                return new IntList(d*d,SquareNonDestructive(L.tail));
        }
       
        public static IntList reverseNonDestructive(IntList L) {
                IntList N = null;
                while (L!=null){
                        N = new IntList(L.tail,N);
                        L = L.tail;
                }
                return N;
        }
        public static void reverseDestructive(IntList L) {
                IntList tmp = L.tail;
                L.tail = null;
                IntList p;
                while (tmp!=null){
                        p = tmp.tail;
                        tmp.tail = L;
                        L = tmp;
                        tmp = p;               
                }
        }
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

whosays 发表于 2015-6-12 04:35:04 | 显示全部楼层
/** Solution to Discussion 2, CS 61B 2015Sprin **/

/** Squaring a list **/
public class IntList {
   public int head;
   public IntList tail;
   public IntList(int h, IntList t) {
      head = h;
      tail = t;
   }
   
   // Squaring a list
   // Destructively, iteratively
   public static IntList SquareDestructive(IntList L) {
      while (L != null) {
         L.head = L.head * L.head;
         L = L.tail;
     }
     return L;
   }

   /** Non-destructively squares each element of the given IntList L.
* Don’t modify the given IntList.
* Should be written recursively*/
   public static IntList SquareNonDestructive(IntList L) {
      if (L.tail == null) {
         return new IntList(L.head * L.head, null);
      }
      return new IntList (L.head * L.head, SquareNonDestructive(L.tail));
   }

   // Destructively, recursion
   public static IntList SquareDestructiveRec (IntList L) {
      L.head = L.head * L.head;
      if (L.tail == null) {
         return L;
      }
      L.tail = SquareDestructiveRec(L.tail);
      return L;
   }

   // Nondestructively, iteratively
   public static IntList SquareNonDestructiveIte (IntList L) {
      IntList CopyList = new IntList (L.head, new IntList (L.tail.head, L.tail.tail));
      while (CopyList != null) {
         CopyList.head = CopyList.head * CopyList.head;
         CopyList = CopyList.tail;
      }
      return CopyList;
   }

   // Reversing Linked Lists
   /** Takes in an IntList and non-destructively returns an IntList whose
elements have been reversed.*/
   public static IntList reverseNonDestructive(IntList lst) {
      IntList CopyList = new IntList (lst.head, new IntList (lst.tail.head, lst.tail.tail));
      IntList prev = null;
      while (CopyList != null) {
         IntList temp = CopyList.tail;
         CopyList.tail = prev;
         prev = CopyList;
         CopyList = temp;
      }
      return CopyList;
   }

   
   // Main function needs to be modified to fit the tests
   public static void main(String[] args) {
      
   }
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

a0106660 发表于 2015-6-12 19:11:36 | 显示全部楼层
我设了个临时指正temp,没有把原来linklist头指针改变,方便写程序验证。bonus 还在思考中。。。

更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Casualet 发表于 2015-6-16 19:37:57 | 显示全部楼层
本帖最后由 Casualet 于 2015-6-16 19:43 编辑
a0106660 发表于 2015-6-12 19:11
我设了个临时指正temp,没有把原来linklist头指针改变,方便写程序验证。bonus 还在思考中。。。

回复错地方了,忽略我=_=
回复 支持 反对

使用道具 举报

Casualet 发表于 2015-6-16 19:41:27 | 显示全部楼层
本帖最后由 Casualet 于 2015-6-16 19:43 编辑

IMG_20150616_192042.jpg
public class d2{

    public static IntList SquareDestructive(IntList l){
        if(l.tail==null){
             l.head=l.head*l.head;
             return null;
        }  
        l.head=l.head*l.head;
        SquareDestructive(l.tail);
        return l;
    }//recursive

     
    public static IntList SquareDestructiveV2(IntList l){
        IntList L=l;
       while(l.tail!=null){
          l.head=l.head*l.head;
          l=l.tail;
       }  
          l.head=l.head*l.head;
        return L;
    }//iterative

    public static IntList SquareNonDestructive(IntList l){
           if(l.tail==null)
              return new IntList(l.head*l.head,null);
           return new IntList(l.head*l.head,SquareNonDestructive(l.tail));            
           

    }//recursive
   
   public static IntList SquareNonDestructiveV2(IntList l){
         IntList L,next,temp;
         L=new IntList(l.head*l.head,null);
         next=L;              
         while(l.tail!=null){
           l=l.tail;
           temp= new IntList(l.head*l.head,null);
           next.tail=temp;
           next=next.tail;
       }
       //  next.tail=new IntList(l.head*l.head,null);   
        return L;
   }//iterative

   public static IntList reverseNonDestructive(IntList lst){
         IntList cur,next,myCur,myNext=null;
         cur=lst;
         next=cur.tail;
         myCur=new IntList(cur.head,null);
         if(next==null) return myCur;
         while(next!=null){              
          myNext=new IntList(next.head,null);
          myNext.tail=myCur;
          myCur=myNext;
          cur=cur.tail;
          next=next.tail;           
        }

          return myNext;
    }
   
    public static IntList reverseDestructive(IntList lst){
          IntList cur,next,nextTemp;
          cur=lst;
          next=cur.tail;
          cur.tail=null;
          if(next==null) return cur;
          while(next!=null){
            if(next.tail!=null){
                nextTemp=next.tail;
                next.tail=cur;
                cur=next;
                next=nextTemp;   
           }else{

             break;
         }
            
               
       }
          next.tail=cur;
          return next;
              
    }

    public static void printList(IntList l){
       while(l.tail!=null){
            System.out.print(l.head+" ");
            l=l.tail;
       }
            System.out.println(l.head);   
      
    }

    public static void main(String args[]){
                     
          IntList l=new IntList(4,null);
          l=new IntList(3,l);
          l=new IntList(2,l);
          l=new IntList(1,l);   

          printList(l);
          SquareDestructive(l);
          printList(l);
          SquareDestructiveV2(l);
          printList(l);
          IntList L=SquareNonDestructive(l);
          printList(L);
          L=SquareNonDestructive(L);
          printList(L);
          L= reverseNonDestructive(L);
          printList(L);
          L= reverseDestructive(L);
          printList(L);         

}
} 测试.png
第一题不知道为什么倒了;图片是测试结果,0是因为overflow; V2表示的是bonus版本;

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

西风吹草 发表于 2015-6-19 06:19:12 | 显示全部楼层
2a.
        public static IntList SquareDestructive(IntList L){
                IntList M = L;
                while (L != null){
                        L.head = L.head * L.head;
                        L = L.tail;
                }
                return M;
        }

2b.
        public static IntList SquareNonDestructive(IntList L){
                if (L == null){
                        return null;
                }else{
                        return new IntList(L.head * L.head, SquareNonDestructive(L.tail));
                }
        }

3a.
        public static IntList reverseNonDestructive(IntList lst){
                IntList M = new IntList(lst.head, null);
                IntList N = lst.tail;
                int i = 1;
                while (i < lst.size()){
                        M = new IntList(N.head, M);
                        N = N.tail;
                        i += 1;                       
                }
                return M;
        }

3b.
        public static void reverseDestructive(IntList L) {
                int i = 1;
                while (i < L.size()){
                        move0thToNth(L, L.size() - i);
                        i += 1;
                }
    }
       
        public static void exchangeTheFirstTwo(IntList lst){
                int temp = lst.head;
                lst.head = lst.tail.head;
                lst.tail.head = temp;
                //return lst;
        }
       
        public static void move0thToNth(IntList lst, int n){
                if (n != 0){
                        exchangeTheFirstTwo(lst);
                        move0thToNth(lst.tail, n - 1);
                }
        }

最后一题我自己又建了两个函数,方法略显麻烦。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

ilyak 发表于 2015-6-25 16:19:34 | 显示全部楼层
求帮助啊啊啊啊啊啊,一个问题是square的destructive iteratively里面,最后需要return L么,我觉得这个时候应该没有L可以return了,最后一个L=L.tail的时候,L已经是null了?有点混乱
还有一个就是后面reverse的,代码如下
public static IntList reverseNonDestructive(IntList L){
  //IntList N=new IntList();
  Intlist N=null;
  N.tail=new IntList(L.head,null);
  L=L.tail;
  while(L.tail!=null){
    N.tail=new IntList(L.head,N.tail);
    L=L.tail;
  }
  N=N.tail;
  return N;
}


测试的时候永远报错啊永远报错,原因是

non-static variable this cannot be referenced from a static context

是因为new的关系么!!!我已经混乱了什么时候要new什么时候不用了。。。求帮助QWQ
回复 支持 反对

使用道具 举报

pigeyes 发表于 2015-7-29 17:58:38 | 显示全部楼层
最後的bonus想到一個覺得不是很有效率的方法....
更多图片 小图 大图
组图打开中,请稍候......
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-26 04:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表