From CSULA CS Wiki
Jump to: navigation, search
m
 
Line 121: Line 121:
  
 
</li></ol>
 
</li></ol>
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
<div  style="display:none">
 
[We are delicate. We do not delete your content.]
 
[l_sp4]
 
 
 
[http://www.buddyprofile.com/viewprofile.php?username=waterfordcrystal waterford crystal]
 
[http://www.buddyprofile.com/viewprofile.php?username=swarovskicrystal swarovski crystal bead]
 
[http://www.buddyprofile.com/viewprofile.php?username=mesotheliomalawsuits mesothelioma lawsuits]
 
[http://www.buddyprofile.com/viewprofile.php?username=mesotheliomasymptoms mesothelioma symptoms]
 
[http://www.buddyprofile.com/viewprofile.php?username=mesotheliomadiag mesothelioma diagnosis]
 
[http://www.buddyprofile.com/viewprofile.php?username=wacoalbras wacoal bras]
 
[http://www.buddyprofile.com/viewprofile.php?username=teenbra teen bra]
 
[http://www.buddyprofile.com/viewprofile.php?username=unsecuredloan unsecured signature loan]
 
[http://www.buddyprofile.com/viewprofile.php?username=homeloans Countrywide Home Loans]
 
[http://blog.moddingplanet.it/?w=formalpromdresses Formal Prom Dresses]
 
[http://blog.moddingplanet.it/?w=sexypromdress Sexy Prom Dress]
 
[http://blog.moddingplanet.it/?w=cocktaildresses cocktail dresses]
 
[http://www.buddyprofile.com/viewprofile.php?username=telmobile TMobile]
 
[http://www.buddyprofile.com/viewprofile.php?username=watersoftener water softener]
 
[http://www.buddyprofile.com/viewprofile.php?username=tanklesswaterheater tankless water heater]
 
[http://www.buddyprofile.com/viewprofile.php?username=rockportshoes rockport shoes]
 
[http://www.buddyprofile.com/viewprofile.php?username=osmosiswaterfilter reverse osmosis water filter]
 
[http://www.buddyprofile.com/viewprofile.php?username=merrellshoes merrell shoes]
 
[http://www.buddyprofile.com/viewprofile.php?username=oscardresses oscar dresses]
 
[http://www.buddyprofile.com/viewprofile.php?username=easterdresses easter dresses]
 
[http://flyfone.blox.pl/resource/flyfonevoip.htm flyfone voip]
 
[http://www.buddyprofile.com/viewprofile.php?username=plussizepromdresses plus size prom dresses]
 
[http://www.buddyprofile.com/viewprofile.php?username=discountpromdresses discount prom dresses]
 
[http://blog.moddingplanet.it/?w=hooterscasinolas Hooters Casino Las Vegas]
 
[http://blog.moddingplanet.it/?w=grandcasinomille grand casino mille lacs]
 
[http://blog.moddingplanet.it/?w=lasvegascasino las vegas casino coupons]
 
[http://blog.moddingplanet.it/?w=onlinepokeraide online poker aide]
 
[http://www.donx.de/blog/pechangacasino pechanga casino]
 
[http://www.donx.de/blog/grandvictoriacasino/ grand victoria casino]
 
[http://www.donx.de/blog/ballgowns/ ball gowns]
 
[http://www.privetparis.com/blog/rtgcasinobonus/ rtg casino bonus]
 
 
[http://blog.moddingplanet.it/?w=rtgcasinobonus rtg casino bonus]
 
[http://blog.moddingplanet.it/?w=grandcasinocoushat grand casino coushatta]
 
[http://blog.moddingplanet.it/?w=grandcasinohinckle grand casino hinckley]
 
[http://blog.moddingplanet.it/?w=isleofcapricasino isle of capri casino]
 
[http://blog.moddingplanet.it/?w=mohegansuncasino mohegan sun casino]
 
[http://blog.moddingplanet.it/?w=palacasino pala casino]
 
[http://blog.moddingplanet.it/?w=roulettewheels roulette wheels]
 
[http://blog.moddingplanet.it/?w=winstarcasino winstar casino]
 
[http://blog.moddingplanet.it/?w=cheappromdresses Cheap Prom Dresses]
 
[http://blog.moddingplanet.it/?w=informalweddingdre informal wedding dresses]
 
[http://blog.moddingplanet.it/?w=oscardresses oscar dresses]
 
[http://blog.moddingplanet.it/?w=eveninggowns evening gowns]
 
</div>
 

Latest revision as of 15:21, 22 May 2006

Homework 5

  1. In prolog mod is the mod function.
    ?- X is 23 mod 20.
    X = 3.

    Use the range/3 predicate and the mod function to generate a list of the divisors of a number.

    ?- divisors(28, Ds).
    Ds = [1, 2, 4, 7, 14]
    range(High, High, [High]).
    range(Low, High, [Low|Rest]) :- Low @=< High, Next is Low+1, range(Next, High, Rest).
    
    divisors(D, Ds) :- X is D - 1, range(1, X, R), divisors_help(R, D, Ds).
    divisors_help([], _, []).
    divisors_help([H|T], D, [H|Ds]) :- X is D mod H, X = 0, divisors_help(T, D, Ds).
    divisors_help([H|T], D, Ds) :- X is D mod H, X \= 0, divisors_help(T, D, Ds).
    
  2. Do the homework at the end of Prolog and graphs by using the following strategy.
    • See if there is a path of length 0.
    • If not, see if there is a path of length 1.
    • If not, see if there is a path of length 2.
    • If not, see if there is a path of length 3. Etc. This strategy is known as Generate and Test. You are generating the integers in sequence and then testing to see if there is a path of that length. You continue to do that until you find a path or you determine that no path is possible. In some cases you might simply search forever. (You will learn about this in CS 486.)
    • Use something like is_integer/1 to generate successively larger integers.
    • Assume you know the total number of edges in the graph. Don't allow the possible length of the path to exceed the total number of edges. That is, as you increment the possible path length, don't allow it to exceed the total number of edges. If no path is found, fail.
    • On backtracking generate longer and longer paths up to the limit of the maximum possible path length. When no further paths less than or equal to the maximum are found, fail. Given the data in Prolog and graphs, the following is one possible output.
    ?- shortestPath(1, 5, Path).
    
    Path = [1, 2, 5] ;
    
    Path = [1, 4, 5] ;
    
    Path = [1, 3, 5] ;
    
    Path = [1, 2, 3, 5] ;
    
    Path = [1, 4, 3, 5] ;
    
    Path = [1, 3, 4, 5] ;
    
    Path = [1, 3, 2, 5] ;
    
    Path = [1, 2, 3, 4, 5] ;
    
    Path = [1, 4, 3, 2, 5] ;
    
    No
    
    ?- 
    


    /* prolog tutorial 2.15 Graph structures and paths */
    
    edge(1,2).
    edge(1,4).
    edge(1,3).
    edge(2,3).
    edge(2,5).
    edge(3,4).
    edge(3,5).
    edge(4,5).
    
    connected(X,Y) :- edge(X,Y) ; edge(Y,X).
    
    path(A,B,Path) :-
          travel(A,B,[A],Q), 
          reverse(Q,Path).
    
    travel(A,B,P,[B|P]) :- 
          connected(A,B).
    travel(A,B,Visited,Path) :-
          connected(A,C),           
          C \== B,
          \+member(C,Visited),
          travel(C,B,[C|Visited],Path). 
    
    shortestPath(A, B, Path) :- shortestPath_help(A, B, Path, 0, 8). /* assume 8 is total number of edges */
    shortestPath_help(A, B, Path, S, L) :- X is L - 1, S =< L, shortestPath_help(A, B, Path, S, X).
    shortestPath_help(A, B, Path, _, L) :- path(A, B, Path), length(Path, L).
    
  3. To avoid backtracking forever once one finds the longest possible path, you will have to modify is_integer/1 so that it fails when it reaches a limit. That is, convert is_integer/1 to be is_integer(+Max, ?Int), which on backtracking returns in Int all integers less than or equal to Max.
    ?- is_integer2(6, Int).
    
    Int = 0 ; 
    
    Int = 1 ;
    
    Int = 2 ;
    
    Int = 3 ;
    
    Int = 4 ;
    
    Int = 5 ;
    
    Int = 6 ;
    
    No
    
    ?- 
    


    is_integer2(Max, Int) :- is_integer2_help(0, Max, Int).
    is_integer2_help(S, Max, Int) :- X is Max - 1, S < Max, is_integer2_help(S, X, Int).
    is_integer2_help(_, Max, Int) :- Int = Max.
    
  4. Use generate and test to find (on backtracking) all perfect integers—i.e., integers which are the sum of their divisors.
    ?- is_perfect(X).
    
    X = 6;
    
    X = 28; …
    
    sum([], 0).
    sum([H|T], Sum) :- sum(T, S), Sum is S + H.
    
    is_perfect(X) :- is_perfect_help(6, X).
    is_perfect_help(A, X) :- divisors(A, Ds), sum(Ds, S), S = A, X = A.
    is_perfect_help(A, X) :- divisors(A, Ds), sum(Ds, S), S = A, B is A + 1, is_perfect_help(B, X).
    is_perfect_help(A, X) :- divisors(A, Ds), sum(Ds, S), S \= A, B is A + 1, is_perfect_help(B, X).