Laboration 4 a med smak av matematik och algoritmer

  1. Skriv en metod som sorterar en lista av strängar med avseende på strängarnas längd. En kortare sträng kommer alltså före en längre sträng i ordningen. Skriv ett program som testar metoden genom att kopiera över argv till en lista, sortera listan och skriva ut resultatet. Se klassen ArrayList med metoder för att lägga till, läsa av och plocka bort ur listan.

  2. Skriv ett program som beräknar och skriver ut antalet primtalstvillingar mindre än 1000000. En primtalstvilling är ett par (k,k+2) av heltal där både k och k+2 är primtal. (Svar: 8169)

  3. Använd klassen java.math.BigInteger för att skriva ett program som givet ett positivt heltal n på kommandoraden beräknar och skriver ut det exakta värdet av
    1 + 1/2 + 1/3 + .... +1/n
    
    som ett bråk i förkortad form (dvs som m/n, där m och n är positiva heltal vars största gemensamma delare är 1).

  4. En faroblandning (perfekt riffelblandning) av en kortlek går till på följande vis: kortleken kuperas precis på mitten så att man får två högar k1,..,k26 och k27,k28,..,k52. Därefter slås högarna ihop så att man omväxlande tar ett kort från vardera högen, med början i den första: k1,k27,k2,k28,...,k26,k52. Skriv ett program som räknar ut hur många faroblandningar som krävs för att kortleken ska återfå sin ursprungliga ordning. (Svar: 8)

  5. Skriv ett program Orm som fungerar på följande sätt. När programmet anropas med ett argument på kommandoraden som är en sträng innehållande tecknen / \ ritas en motsvarande slingrande orm ut på skärmen. Vad detta betyder illustreras bäst av ett par exempel:
    > java Orm "\/\\\\\////"
    \
    /
    \
     \
      \
       \
        \
        /
       /
      /
     /
    > java Orm "\\\\\\\\\\\///\\\/\/\/\\\/"
    \
     \
      \
       \
        \
         \
          \
           \
            \
             \
              \
              /
             /
            /
            \
             \
              \
              /
              \
              /
              \
              /
              \
               \
                \
                /
    > 
    
    Om ormen skulle hamna utanför raden vid utskrift (förutsätt en radlängd på 80 tecken) hoppas motsvarande tecken i strängen bara över. Likaså hoppas alla tecken i strängen som inte är \ eller / bara över. Inga felmeddelanden behöver ges av programmet

  6. Skriv ett program som skriver ut alla permutationer av tecknen i en sträng på kommandoraden. Till exempel ska anropet
    java Perm abc
    
    ge till exempel utskriften
    
    abc
    acb
    bac
    bca
    cba
    cab
    
    eller vilken som helst annan utskrift som i någon godtycklig ordning ger samtliga permutationer.

  7. Skriv en rekursiv metod
    public static double summa(int n){...
    
    som beräknar summan av 1/1 + 1/2 + ... + 1/n där n är ett positivt heltal. Skriv en main-metod som demonstrerar metoden på lämpligt sätt, t.ex.
    public static void main(String argv[]){
        int n = Integer.parseInt(argv[0]);
        System.out.println("Summan = " + summa(n));
    }
    

  8. (Redovisning) Denna laboration är delvis helt nydefinierad. Om du tycker att något är tvetydigt ska du meddela mig så att instruktionen blir klarare. Detta innebär att nedanstående text kanske kommer att kompletteras under kursens gång. Grundförutsättningarna kommer dock att bestå!

    Definiera en klass Math som innehåller två metoder:

    public static double newtonRaphson(double x0, double a, double b, 
                                       double c, double dx){...}
    
    public static TwoValues linearRegression(double[] x, double[] y){...}
    

    Den första metoden beräknar nollstället för funktionen y = ax2 + bx + c och returnerar svaret. Svarets noggrannhet bestäms av dx. Se Newton-Raphson's metod. Den andra metoden returnerar två värden inneslutna i en klass TwoValues som är given här:

    /*
     * This class contains the values a and b, for example describing
     * "räta linjens ekvation": y = a*x + b
     */
    public class TwoValues{
        public double a; 
        public double b;
    }
    
    Dessa två värden beskriver en funktion y = ax + b, d.v.s. regressionslinjen anpassad med minsta kvadratmetoden. Se Linjär regression.

    Newton-Raphson's metod

    Den första metoden tar startvärdet x0, andragradskoeff. a, förstagradskoeff. b, konstanten c och slutdifferensen dx och returnerar en approximativ lösning till ekvationen

    med hjälp av Newton-Raphsons metod för att hitta en funktions skärning med x-axeln. Skriv med andra ord en metod som implementerar numerisk ekvationslösning (Newton-Raphsons formel) . Argumentet dx avgör hur många gånger programmet ska iterera så att skillnaden mellan xn och xn+1 är tillräckligt liten för att lösningen skall accepteras. Fötydligande: Användaren skall alltså inte mata in antalet iterationer, utan programmet skall iterera tills ett tillräckligt exakt värde på dx hittats. Pröva dig fram till bra värden. Alla funktioner förutsätts ha nollställen, så du behöver inte ägna någon uppmärksamhet åt komplexa rötter och annat elände. Den som använder metoden måste alltså själv veta att funktionen given av argumenten a, b och c inte saknar nollställe.

    Ett tips är att approximera derivatan med följande formel:

    Linjär regression

    Linjen som bäst passar n koordinater (x1, y1), (x2, y2), . . ., (xn, yn) kallas regressionslinjen och uttrycks som:

    där

    Det finns många olika demonstrationer av detta problem på nätet. Här finns ett exempel på linjär regression.