Euler Project – Problem 25 solution

1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

Answer:4782

Solution

public class Problem25 {

    public static void main(String[] args) {

        String a = "1";
        String b = "1";
       
        int count = 2;
        while(b.length()<1000)
        {
            System.out.println("index "+count+":"+b.length()+"digits");
            String temp = b;
            b = sum(a,b);
            a = temp;
            count++;
        }

        System.out.println(count);

    }

    public static String sum(String a, String b) {

        char[] a_digits = a.toCharArray();
        char[] b_digits = b.toCharArray();

        String sum = "";
        boolean remainder = false;
        for (int i = 0; i < a_digits.length; i++) {
            char a_digit = a_digits[a_digits.length - i - 1];
            char b_digit = b_digits[b_digits.length - i - 1];

            int a_int = Integer.parseInt(String.valueOf(a_digit));
            int b_int = Integer.parseInt(String.valueOf(b_digit));

            int s = a_int + b_int;
            if (remainder) {
                s++;
            }
            remainder = (s>=10);
           
            String s_str = String.valueOf(s);
            String last_digit = s_str.substring(s_str.length()-1);
            sum = last_digit+sum;
        }
       
        int beginning = 0;
        if(b.length()>a.length())
        {
            beginning=Integer.parseInt(b.substring(0,1));
        }
        if(remainder)
        {
            beginning++;
        }
        if(beginning>0)
        {
            sum = beginning + sum;
        }
       

        return sum;
    }

}

Android – Book page pagination example

In this tutorial I will show how to divide some text into pages. . So let’s start:

Create new Android application project. And your layout(activity_main.xml) for your activity should look like this:

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
   xmlns:tools="http://schemas.android.com/tools"
   android:layout_width="match_parent"
   android:layout_height="match_parent"
   tools:context=".MainActivity"
   android:background="#FFFFFF">

    <TextView
       android:id="@+id/tvContent"
       android:layout_width="match_parent"
       android:layout_height="match_parent"
       android:textSize="24sp"
       android:textColor="#000000"
       android:layout_margin="24dp"/>

    <LinearLayout
       android:layout_width="match_parent"
       android:layout_height="match_parent"
       android:orientation="horizontal">

        <LinearLayout
           android:id="@+id/previous"
           android:layout_width="0dp"
           android:layout_height="match_parent"
           android:layout_weight="1"
           android:orientation="horizontal" />

        <LinearLayout
           android:id="@+id/next"
           android:layout_width="0dp"
           android:layout_height="match_parent"
           android:layout_weight="1"
           android:orientation="horizontal" />

    </LinearLayout>

</RelativeLayout>

Next step is to create new class and name it: Pagination.java

package net.joerichard.bookpaginationexample;

import android.text.Layout;
import android.text.StaticLayout;
import android.text.TextPaint;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by joe on 03.09.15.
 */

public class Pagination {
    private final boolean mIncludePad;
    private final int mWidth;
    private final int mHeight;
    private final float mSpacingMult;
    private final float mSpacingAdd;
    private final CharSequence mText;
    private final TextPaint mPaint;
    private final List<CharSequence> mPages;

    public Pagination(CharSequence text, int pageW, int pageH, TextPaint paint, float spacingMult, float spacingAdd, boolean inclidePad) {
        this.mText = text;
        this.mWidth = pageW;
        this.mHeight = pageH;
        this.mPaint = paint;
        this.mSpacingMult = spacingMult;
        this.mSpacingAdd = spacingAdd;
        this.mIncludePad = inclidePad;
        this.mPages = new ArrayList<CharSequence>();

        layout();
    }

    private void layout() {
        final StaticLayout layout = new StaticLayout(mText, mPaint, mWidth, Layout.Alignment.ALIGN_NORMAL, mSpacingMult, mSpacingAdd, mIncludePad);

        final int lines = layout.getLineCount();
        final CharSequence text = layout.getText();
        int startOffset = 0;
        int height = mHeight;

        for (int i = 0; i < lines; i++) {
            if (height < layout.getLineBottom(i)) {
                // When the layout height has been exceeded
                addPage(text.subSequence(startOffset, layout.getLineStart(i)));
                startOffset = layout.getLineStart(i);
                height = layout.getLineTop(i) + mHeight;
            }

            if (i == lines - 1) {
                // Put the rest of the text into the last page
                addPage(text.subSequence(startOffset, layout.getLineEnd(i)));
                return;
            }
        }
    }

    private void addPage(CharSequence text) {
        mPages.add(text);
    }

    public int size() {
        return mPages.size();
    }

    public CharSequence get(int index) {
        return (index >= 0 && index < mPages.size()) ? mPages.get(index) : null;
    }
}

Using Pagination, we will divide book text into pages.
MainActivity:

package net.joerichard.bookpaginationexample;

import android.os.Build;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.text.Html;
import android.text.Spanned;
import android.text.TextUtils;
import android.view.Menu;
import android.view.MenuItem;
import android.view.View;
import android.view.ViewTreeObserver;
import android.widget.LinearLayout;
import android.widget.TextView;

public class MainActivity extends AppCompatActivity {

    Pagination mPagination;
    CharSequence mText;
    int mCurrentIndex = 0;
    TextView tvContent;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 100; i++) {
            sb.append("This text helps to create some bulk content. ");
        }
        String book_content = sb.toString();

        Spanned htmlString = Html.fromHtml(book_content);
        mText = TextUtils.concat(htmlString);

        tvContent = (TextView) findViewById(R.id.tvContent);
        tvContent.getViewTreeObserver().addOnGlobalLayoutListener(new ViewTreeObserver.OnGlobalLayoutListener() {
            @Override
            public void onGlobalLayout() {
                // Removing layout listener to avoid multiple calls
                if (Build.VERSION.SDK_INT < Build.VERSION_CODES.JELLY_BEAN) {
                    tvContent.getViewTreeObserver().removeGlobalOnLayoutListener(this);
                } else {
                    tvContent.getViewTreeObserver().removeOnGlobalLayoutListener(this);
                }
                mPagination = new Pagination(mText,
                        tvContent.getWidth(),
                        tvContent.getHeight(),
                        tvContent.getPaint(),
                        tvContent.getLineSpacingMultiplier(),
                        tvContent.getLineSpacingExtra(),
                        tvContent.getIncludeFontPadding());
                update();
            }
        });

        LinearLayout previous = (LinearLayout) findViewById(R.id.previous);
        previous.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                if (mCurrentIndex > 0) {
                    mCurrentIndex--;
                    update();
                }
            }
        });

        LinearLayout next = (LinearLayout) findViewById(R.id.next);
        next.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                if (mCurrentIndex < mPagination.size()) {
                    mCurrentIndex++;
                    update();
                }
            }
        });

    }

    private void update() {
        final CharSequence text = mPagination.get(mCurrentIndex);
        if (text != null) tvContent.setText(text);
    }

}

That’s it. Let’s run application!
Снимок экрана 2015-09-13 в 18.06.35