Commits

Eric Chen committed 52bf23e

Add some solutions.

Comments (0)

Files changed (15)

lyxSrc/proEu3.lyx

+#LyX 2.0 created this file. For more info see http://www.lyx.org/
+\lyxformat 413
+\begin_document
+\begin_header
+\textclass article
+\begin_preamble
+\usepackage[T1]{fontenc}
+\usepackage{pslatex}
+\date{}
+\usepackage{footnote}
+\makesavenoteenv{tabular}
+\end_preamble
+\use_default_options true
+\maintain_unincluded_children false
+\language english
+\language_package default
+\inputencoding default
+\fontencoding global
+\font_roman default
+\font_sans default
+\font_typewriter default
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100
+\font_tt_scale 100
+
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize a4paper
+\use_geometry true
+\use_amsmath 1
+\use_esint 1
+\use_mhchem 1
+\use_mathdots 1
+\cite_engine basic
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\use_refstyle 1
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\leftmargin 2.5cm
+\topmargin 3cm
+\bottommargin 2.5cm
+\footskip 1cm
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\quotes_language english
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Subsection
+Prerequisite
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset href
+LatexCommand href
+name "The problem of Cycle detection"
+target "http://en.wikipedia.org/wiki/Cycle_detection"
+
+\end_inset
+
+.
+ There are several ways to solve cycle detection problem:
+\end_layout
+
+\begin_layout Standard
+(1) 
+\begin_inset CommandInset href
+LatexCommand href
+name "Floyd's cycle-finding algorithm"
+target "http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare"
+
+\end_inset
+
+: To understand this section, the author actually writes 
+\begin_inset Quotes eld
+\end_inset
+
+x
+\begin_inset script subscript
+
+\begin_layout Plain Layout
+i
+\end_layout
+
+\end_inset
+
+= x
+\begin_inset script subscript
+
+\begin_layout Plain Layout
+i + kλ
+\end_layout
+
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+ at the beginning rather than 
+\begin_inset Quotes eld
+\end_inset
+
+x
+\begin_inset script subscript
+
+\begin_layout Plain Layout
+i
+\end_layout
+
+\end_inset
+
+= x
+\begin_inset script subscript
+
+\begin_layout Plain Layout
+i
+\end_layout
+
+\end_inset
+
++kλ
+\begin_inset Quotes erd
+\end_inset
+
+.
+ He also writes: 
+\begin_inset Quotes eld
+\end_inset
+
+In particular, whenever i =kλ
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+When i==kλ, that means tortoise at location kλ and hare at location 2kλ.
+ Since there exists a cycle, so (kλ-13)%λ==(2kλ-13)%λ, which indicates that
+ x
+\begin_inset script subscript
+
+\begin_layout Plain Layout
+i
+\end_layout
+
+\end_inset
+
+==x
+\begin_inset script subscript
+
+\begin_layout Plain Layout
+2i
+\end_layout
+
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+
+\begin_inset Formula $\geq$
+\end_inset
+
+μ, it follows that x
+\begin_inset script subscript
+
+\begin_layout Plain Layout
+i
+\end_layout
+
+\end_inset
+
+=x
+\begin_inset script subscript
+
+\begin_layout Plain Layout
+2i
+\end_layout
+
+\end_inset
+
+.
+\begin_inset Foot
+status collapsed
+
+\begin_layout Plain Layout
+cause hare's speed is always twice as tortoise's
+\end_layout
+
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Assume we have 13 elements before we enter the cycle, which is of length
+ 5.
+ An concrete example:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Tabular
+<lyxtabular version="3" rows="4" columns="12">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<column alignment="center" valignment="top" width="0">
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+element index
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1~13
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+14
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+15
+\begin_inset Foot
+status collapsed
+
+\begin_layout Plain Layout
+This is μ, and also is i==kλ
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+16
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+17
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+18
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+19
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+20
+\begin_inset Foot
+status collapsed
+
+\begin_layout Plain Layout
+This is i==kλ
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+21
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+22
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+23
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+tortoise location
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1~13
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+14
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+15
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+16
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+17
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+18
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+19
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+20
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+21
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+22
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+23
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+hare location
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2~26 with step 2
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+28
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+30
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+32
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+34
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+36
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+38
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+40
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+42
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+44
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+46
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+hare loc in loop
+\begin_inset Foot
+status collapsed
+
+\begin_layout Plain Layout
+cause hare is already in the cycle so the value for each index are repeated.
+ For ex, element at index 28==element at index 18
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+...
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+18
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+15
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+17
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+14
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+16
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+18
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+15
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+17
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+14
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+16
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+(2) 
+\begin_inset CommandInset href
+LatexCommand href
+name "Barent's Cycle Finding algorithm"
+target "http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm"
+
+\end_inset
+
+: 
+\end_layout
+
+\begin_layout Subsection
+Main algorithm for solving the problem on hand
+\end_layout
+
+\begin_layout Standard
+Based on 
+\begin_inset CommandInset href
+LatexCommand href
+name "Pollard's rho Algorithm"
+target "http://en.wikipedia.org/wiki/Pollard's_rho_algorithm#Core_ideas"
+
+\end_inset
+
+ 
+\begin_inset Foot
+status collapsed
+
+\begin_layout Plain Layout
+In Pollar's rho alg webpage, it says:
+\begin_inset Quotes erd
+\end_inset
+
+ two numbers x and y are congruent modulo p(i.e.
+ (x-y)==p*N) with probability 0.5 after 1.177
+\begin_inset Formula $\sqrt{p}$
+\end_inset
+
+ numbers have been randomly chosen.
+\begin_inset Quotes erd
+\end_inset
+
+ Where does this 1.177
+\begin_inset Formula $\sqrt{p}$
+\end_inset
+
+ come from? Well you have to read 
+\begin_inset CommandInset href
+LatexCommand href
+name "Birthday Problem"
+target "http://en.wikipedia.org/wiki/Birthday_problem#Generalizations"
+
+\end_inset
+
+, in which var d is var p(in Pollar's rho alg) so n(d)~=
+\begin_inset Formula $\sqrt{2d*naturalLog(2)}$
+\end_inset
+
+~=1.177
+\begin_inset Formula $\sqrt{d}$
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document

src/NCKUAlg/ProgHW4/dynamicTable/dynamic.c

+/*
+ * Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+AlgNCKU@gmail.com)
+ * This file is a part of AlgNCKU.
+ *
+ * AlgNCKU is a free software; you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option)
+ * any later version.
+ *
+ * This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
+ * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with this source file; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ */
+#include <stdio.h>
+#include <stdlib.h>
+void printTable(int *ptr, int end, FILE *outputFile);
+int main(int argc, char *argv[]) {
+	char *inputFileName, *outputFileName;
+	if (argc == 1) {
+		inputFileName = "./test2.txt";
+		outputFileName = "./output.txt";
+	} else {
+		inputFileName = argv[1];
+		outputFileName = argv[2];
+	}
+	FILE *inputFile = fopen(inputFileName, "r");
+	FILE *outputFile = fopen(outputFileName, "w");
+	if (inputFile == NULL || outputFile == NULL) {
+		printf("Program terminates because %s can't be found\n", inputFileName);
+		exit(1);
+	}
+	const int maxDigits = 128;
+	char aLine[maxDigits],*numberStr;
+	int *dynamicTablePtr=realloc(NULL,sizeof(int)),*tempPtr=realloc(NULL,sizeof(int)),end=0,maxTableSize=1,number;
+	while (fgets(aLine, sizeof aLine, inputFile) != NULL) //read a line
+	{
+		printf("Command: %s",aLine);
+		fprintf(outputFile, "Command: %s",aLine);
+		numberStr=&aLine[2];
+		number=atoi(numberStr);
+		if(aLine[0]=='a'){
+			if(end+1>maxTableSize){
+				maxTableSize*=2;
+				printf("Increase size of dynamicTable to %d\n",maxTableSize);
+				fprintf(outputFile, "Increase size of dynamicTable to %d\n",maxTableSize);
+				tempPtr=realloc(tempPtr,maxTableSize*sizeof(int));
+				int i;
+				for(i=0;i<end;i++)
+					tempPtr[i]=dynamicTablePtr[i];
+				dynamicTablePtr=realloc(dynamicTablePtr,maxTableSize*sizeof(int));
+				for(i=0;i<end;i++)
+					dynamicTablePtr[i]=tempPtr[i];
+			}
+			dynamicTablePtr[end]=number;
+			printf("Add %d to dynamicTable\n", dynamicTablePtr[end]);
+			fprintf(outputFile, "Add %d to dynamicTable\n", dynamicTablePtr[end]);
+			printTable(dynamicTablePtr,end,outputFile);
+			end++;
+		}else{
+			end--;
+			if(end<maxTableSize/4){
+				maxTableSize/=2;
+				printf("Decrease size of dynamicTable from %d to %d\n",maxTableSize*2,maxTableSize);
+				fprintf(outputFile, "Decrease size of dynamicTable from %d to %d\n",maxTableSize*2,maxTableSize);
+				tempPtr=realloc(tempPtr,maxTableSize*sizeof(int));
+				int i;
+				for(i=0;i<end;i++)
+					tempPtr[i]=dynamicTablePtr[i];
+				dynamicTablePtr=realloc(dynamicTablePtr,maxTableSize*sizeof(int));
+				for(i=0;i<end;i++)
+					dynamicTablePtr[i]=tempPtr[i];
+			}
+			printf("Delete %d in dynamicTable\n", dynamicTablePtr[end]);
+			fprintf(outputFile, "Delete %d in dynamicTable\n", dynamicTablePtr[end]);
+			printTable(dynamicTablePtr,end-1,outputFile);
+		}
+	}
+	fclose(inputFile);
+	fclose(outputFile);
+	return 0;
+}
+void printTable(int *ptr, int end, FILE *outputFile){
+	int i;
+	printf("dynamicTable: [");
+	fprintf(outputFile, "dynamicTable: [");
+	for(i=0;i<end+1;i++){
+		printf(" %d",ptr[i]);
+		fprintf(outputFile, " %d",ptr[i]);
+	}
+	printf(" ]\n\n");
+	fprintf(outputFile, " ]\n\n");
+}
+

src/NCKUAlg/ProgHW4/dynamicTable/test1.txt

+a 1
+a 2
+a 3
+a 4
+a 5
+a 6
+a 7
+a 8
+a 9
+a 10
+a 11
+a 12
+d 12
+d 11
+d 10
+d 9
+d 8
+d 7
+d 6
+d 5
+d 4
+d 3
+d 2

src/NCKUAlg/ProgHW4/dynamicTable/test2.txt

+a 1
+a 2
+a 3
+a 4
+a 5
+a 6
+a 7
+a 8
+a 9
+d 9
+d 8
+d 7
+d 6
+d 5
+d 4
+d 3
+d 2

src/NCKUAlg/ProgHW4/knapsack01/knapsack01.c

+/*
+ * Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+HW4@gmail.com)
+ * This file is a part of HW4.
+ *
+ * HW4 is a free software; you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option)
+ * any later version.
+ *
+ * This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
+ * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with this source file; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ */
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+struct Items {
+	int *WeightsPtr;
+	int *ValuesPtr;
+	int *HowManyPtr;
+	int TotalItemNum;
+	int arrLength;
+	int arrLimit;
+};
+int max(int a, int b);
+int main(int argc, char *argv[]) {
+	char *inputFileName, *outputFileName;
+	if (argc == 1) {
+		inputFileName = "./test2.txt";
+		outputFileName = "./output.txt";
+	} else {
+		inputFileName = argv[1];
+		outputFileName = argv[2];
+	}
+	FILE *inputFile = fopen(inputFileName, "r");
+	FILE *outputFile = fopen(outputFileName, "w");
+	if (inputFile == NULL || outputFile == NULL) {
+		printf("Program terminates because %s can't be found\n", inputFileName);
+		exit(1);
+	}
+	const int maxDigits = 128;
+	char aLine[maxDigits], *numberStr;
+	fgets(aLine, sizeof aLine, inputFile); //get rid of the first line
+	fgets(aLine, sizeof aLine, inputFile); //read knapsack limit
+	int *tempPtr = realloc(NULL, sizeof(int) * 20);
+	struct Items items = { realloc(NULL, sizeof(int) * 20), realloc(NULL,
+			sizeof(int) * 20), realloc(NULL, sizeof(int) * 20), 0, 0, 20 };
+	int knapsackLimit = atoi(aLine), index = 0;
+	printf("Reading input file...\n");
+	fprintf(outputFile, "Reading input file...\n");
+	while (fgets(aLine, sizeof aLine, inputFile) != NULL) //read a line
+	{
+		numberStr = strtok(aLine, " \n");
+		items.WeightsPtr[index] = atoi(numberStr);
+		numberStr = strtok(NULL, " \n");
+		items.ValuesPtr[index] = atoi(numberStr);
+		numberStr = strtok(NULL, " \n");
+		items.HowManyPtr[index] = atoi(numberStr);
+		(items.TotalItemNum) += items.HowManyPtr[index];
+		printf("items: weights=%d, values:%d, howMany:%d\n",
+				items.WeightsPtr[index], items.ValuesPtr[index],
+				items.HowManyPtr[index]);
+		fprintf(outputFile, "items: weights=%d, values:%d, howMany:%d\n",
+				items.WeightsPtr[index], items.ValuesPtr[index],
+				items.HowManyPtr[index]);
+		index++;
+		if (index > items.arrLimit - 1) {
+			(items.arrLimit) *= 2;
+			tempPtr = realloc(items.WeightsPtr, items.arrLimit * sizeof(int));
+			int i;
+			for (i = 0; i < index; i++)
+				tempPtr[i] = items.WeightsPtr[i];
+			items.WeightsPtr = realloc(items.WeightsPtr,
+					items.arrLimit * sizeof(int));
+			for (i = 0; i < index; i++)
+				items.WeightsPtr[i] = tempPtr[i];
+			for (i = 0; i < index; i++)
+				tempPtr[i] = items.ValuesPtr[i];
+			items.ValuesPtr = realloc(items.ValuesPtr,
+					items.arrLimit * sizeof(int));
+			for (i = 0; i < index; i++)
+				items.ValuesPtr[i] = tempPtr[i];
+			for (i = 0; i < index; i++)
+				tempPtr[i] = items.HowManyPtr[i];
+			items.HowManyPtr = realloc(items.HowManyPtr,
+					items.arrLimit * sizeof(int));
+			for (i = 0; i < index; i++)
+				items.HowManyPtr[i] = tempPtr[i];
+		}
+	}
+	fclose(inputFile);
+	int bestValues[items.TotalItemNum + 1][knapsackLimit + 1],
+			addItem[items.TotalItemNum + 1][knapsackLimit + 1];
+	int howManyItemUsed = 0, itemType = 0, totalItemNum, knapsackSize;
+	//!!!!It's crucial to initialize these 2 arrays correctly from "knapsackSize=0" and "totalItemNum=0"
+	for (knapsackSize = 0; knapsackSize <= knapsackLimit; knapsackSize++) { //init first row when there's no item to grab
+		bestValues[0][knapsackSize] = 0;
+		addItem[0][knapsackSize] = 0;
+	}
+	for (totalItemNum = 0; totalItemNum <= items.TotalItemNum; totalItemNum++) { //init first col when knapsackSize==0
+		bestValues[totalItemNum][0] = 0;
+		addItem[totalItemNum][0] = 0;
+	}
+	printf("Solving problem using dynamic programming...\n");
+	fprintf(outputFile, "Solving problem using dynamic programming...\n");
+	for (totalItemNum = 1; totalItemNum <= items.TotalItemNum; totalItemNum++) {
+		if (totalItemNum > items.HowManyPtr[itemType] + howManyItemUsed) { //run out of items of itemType, so start using another type of items
+			howManyItemUsed = totalItemNum - 1;
+			itemType++;
+		}
+		for (knapsackSize = 1; knapsackSize <= knapsackLimit; knapsackSize++) {
+			if (items.WeightsPtr[itemType] <= knapsackSize) {
+				bestValues[totalItemNum][knapsackSize] = max(
+						bestValues[totalItemNum - 1][knapsackSize],
+						items.ValuesPtr[itemType]
+								+ bestValues[totalItemNum - 1][knapsackSize
+										- items.WeightsPtr[itemType]]);
+				/*if bestValues[totalItemNum][knapsackSize]==items.ValuesPtr[itemType]+bestValues[totalItemNum-1][knapsackSize-items.WeightsPtr[itemType]]: this indicates that we'll'get a higher value by replacing
+				 previous item with a "new" item(i.e. items.ValuesPtr[itemType])+ max value that can be attained using the remaining space(i.e. bestValues[totalItemNum-1][knapsackSize-items.Weights[itemType]])
+				 if bestValues[totalItemNum][knapsackSize]==bestValues[totalItemNum-1][knapsackSize]: we'll get a better value by not replacing the previous item with the new item*/
+				addItem[totalItemNum][knapsackSize] =
+						(bestValues[totalItemNum - 1][knapsackSize]
+								> items.ValuesPtr[itemType]
+										+ bestValues[totalItemNum - 1][knapsackSize
+												- items.WeightsPtr[itemType]]) ?
+								0 : 1; //0: do not add new element, 1: add
+			} else { //there's not enough room for adding another item of itemType so keep the previous best
+				bestValues[totalItemNum][knapsackSize] = bestValues[totalItemNum
+						- 1][knapsackSize];
+				addItem[totalItemNum][knapsackSize] = 0;
+			}
+		}
+	}
+	printf("Traverse addItem matrix to obtain the optimal solution...\n");
+	fprintf(outputFile,
+			"Traverse addItem matrix to obtain the optimal solution...\n");
+	//traverse addItem matrix to determine which items should we take
+	int *whichItemToAddPtr = realloc(NULL, sizeof(int) * 20),
+			whichItemToAddSize = 0, whichItemToAddSizeLimit = 20, weightLeft =
+					knapsackLimit;
+	itemType = (index - 1);
+	howManyItemUsed = 0;
+//	whichItemToAdd, weightLeft, itemType, howManyItemUsed := make([]int, 0), knapsackLimit, len(items.Weights)-1, 0
+	for (totalItemNum = items.TotalItemNum; totalItemNum > 0; totalItemNum--) {
+		// fmt.Println("totalItemNum",totalItemNum)
+		// fmt.Println("items.TotalItemNum",items.TotalItemNum)
+		// fmt.Println("itemType",itemType)
+		if (totalItemNum
+				<= items.TotalItemNum - howManyItemUsed
+						- items.HowManyPtr[itemType]) {
+			howManyItemUsed += items.HowManyPtr[itemType];
+			itemType--;
+		}
+		// fmt.Println(itemType)
+		// fmt.Println(weightLeft)
+		if (weightLeft > 0 && addItem[totalItemNum][weightLeft] == 1) {
+			whichItemToAddPtr[whichItemToAddSize] = itemType + 1;
+			if (whichItemToAddSize + 1 > whichItemToAddSizeLimit) {
+				whichItemToAddSizeLimit *= 2;
+				whichItemToAddPtr = realloc(whichItemToAddPtr,
+						whichItemToAddSizeLimit * sizeof(int));
+			}
+			weightLeft -= items.WeightsPtr[itemType];
+			whichItemToAddSize++;
+		}
+	}
+	printf("\nResults:\n");
+	fprintf(outputFile, "\nResults:\n");
+	printf("Optimal value:%d\n", bestValues[items.TotalItemNum][knapsackLimit]);
+	fprintf(outputFile, "Optimal value:%d\n",
+			bestValues[items.TotalItemNum][knapsackLimit]);
+	printf("We need to take items: [");
+	fprintf(outputFile, "We need to take items: [");
+	int count;
+	for (count = 0; count < whichItemToAddSize; count++) {
+		printf(" %d", whichItemToAddPtr[count]);
+		fprintf(outputFile, " %d", whichItemToAddPtr[count]);
+	}
+	printf(" ]\n\n");
+	fprintf(outputFile, " ]\n\n");
+	fclose(outputFile);
+	return 0;
+}
+int max(int a, int b) {
+	if (a > b) {
+		return a; //0 do not add new element
+	} else {
+		return b; //1 add
+	}
+	return -1;
+}

src/NCKUAlg/ProgHW4/knapsack01/knapsack01.go

+//Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+introtoalgorithm3ed@gmail.com)
+//
+//This file is a part of introtoalgorithm3ed.
+//
+//introtoalgorithm3ed is a free software; you can redistribute it and/or modify it under the terms of the GNU General 
+//Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) 
+//any later version.
+//
+//This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the 
+//implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 
+//License for more details.
+//
+//You should have received a copy of the GNU General Public License along with this source file; if not, write to the 
+//Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+
+/*Solve 01 knapsack problem with 3 test cases*/
+package main
+
+import (
+	"fmt"
+	"io/ioutil"
+	"os"
+	"strconv"
+	"strings"
+)
+
+type Items struct {
+	Weights      []int
+	Values       []int
+	HowMany      []int
+	TotalItemNum int
+}
+
+func main() {
+	for _, name := range []string{"./test1.txt", "./test2.txt", "./test3.txt"} {
+		fmt.Println("Running", name)
+		inputFileName := name
+		/*correct sol should be:
+		test1.txt: optimal value=220, items=[3 2]
+		test2.txt: optimal value=15, items=[5 4 3 2]
+		test3.txt: optimal value=36, items=[3 3 3 2 2 2]
+		*/
+		//read whole file into []byte
+		content, err := ioutil.ReadFile(inputFileName)
+		if err != nil {
+			fmt.Println("Gonna exit\n")
+			os.Exit(0)
+		}
+		//maybe use strtok() here when writing C program
+		strContent := strings.Split(string(content), "\n") //convert []byte to a string and split it using \n
+		strContent = strContent[1:]
+		var weight, value, howMany int64
+		weight, _ = strconv.ParseInt(strContent[0], 10, 64)
+		knapsackLimit := int(weight)
+		items := Items{make([]int, len(strContent)-1), make([]int, len(strContent)-1), make([]int, len(strContent)-1), 0}
+		for i := 0; i < len(strContent)-1; i++ {
+			aLine := strings.Fields(strContent[i+1])
+			weight, _ = strconv.ParseInt(aLine[0], 10, 64)
+			value, _ = strconv.ParseInt(aLine[1], 10, 64)
+			howMany, _ = strconv.ParseInt(aLine[2], 10, 64)
+			items.Weights[i], items.Values[i], items.HowMany[i] = int(weight), int(value), int(howMany)
+			items.TotalItemNum += items.HowMany[i]
+		}
+		// fmt.Println("Fin reading input file:", items)
+		//running dynamic programming
+		bestValues, addItem := make([][]int, items.TotalItemNum+1), make([][]int, items.TotalItemNum+1)
+		bestValues[0], addItem[0] = make([]int, knapsackLimit+1), make([]int, knapsackLimit+1)
+		howManyItemUsed, itemType, addOrNot := 0, 0, 0
+		for totalItemNum := 1; totalItemNum <= items.TotalItemNum; totalItemNum++ { //when totalItemNum==0, there's no item to grab
+			if totalItemNum > items.HowMany[itemType]+howManyItemUsed { //run out of items of itemType, so start using another type of items
+				howManyItemUsed = totalItemNum - 1
+				itemType++
+			}
+			bestValues[totalItemNum], addItem[totalItemNum] = make([]int, knapsackLimit+1), make([]int, knapsackLimit+1)
+			for knapsackSize := 1; knapsackSize <= knapsackLimit; knapsackSize++ {
+				if items.Weights[itemType] <= knapsackSize {
+					bestValues[totalItemNum][knapsackSize], addOrNot = max(bestValues[totalItemNum-1][knapsackSize], items.Values[itemType]+bestValues[totalItemNum-1][knapsackSize-items.Weights[itemType]])
+					/*if bestValues[totalItemNum][knapsackSize]==items.Values[itemType]+bestValues[totalItemNum-1][knapsackSize-items.Weights[itemType]]: this indicates that we'll'get a higher value by replacing
+					previous item with a "new" item(i.e. items.Values[itemType])+ max value that can be attained using the remaining space(i.e. bestValues[totalItemNum-1][knapsackSize-items.Weights[itemType]])
+					if bestValues[totalItemNum][knapsackSize]==bestValues[totalItemNum-1][knapsackSize]: we'll get a better value by not replacing the previous item with the new item*/
+					addItem[totalItemNum][knapsackSize] = addOrNot
+				} else { //there's not enough room for adding another item of itemType so keep the previous best
+					bestValues[totalItemNum][knapsackSize] = bestValues[totalItemNum-1][knapsackSize]
+					addItem[totalItemNum][knapsackSize] = 0
+				}
+			}
+		}
+		//traverse addItem matrix to determine which items should we take
+		whichItemToAdd, weightLeft, itemType, howManyItemUsed := make([]int, 0), knapsackLimit, len(items.Weights)-1, 0
+		for totalItemNum := items.TotalItemNum; totalItemNum > 0; totalItemNum-- {
+			// fmt.Println("totalItemNum",totalItemNum)
+			// fmt.Println("items.TotalItemNum",items.TotalItemNum)
+			// fmt.Println("itemType",itemType)		
+			if totalItemNum <= items.TotalItemNum-howManyItemUsed-items.HowMany[itemType] {
+				howManyItemUsed += items.HowMany[itemType]
+				itemType--
+			}
+			// fmt.Println(itemType)
+			// fmt.Println(weightLeft)
+			if weightLeft > 0 && addItem[totalItemNum][weightLeft] == 1 {
+				whichItemToAdd = append(whichItemToAdd, itemType+1)
+				weightLeft -= items.Weights[itemType]
+			}
+		}
+		fmt.Printf("Optimal value:%d\n", bestValues[len(bestValues)-1][len(bestValues[1])-1])
+		fmt.Println("We need to take items:", whichItemToAdd)
+		fmt.Println()
+	}
+}
+
+func max(a, b int) (int, int) {
+	if a > b {
+		return a, 0 //do not add new element
+	} else {
+		return b, 1 //add
+	}
+	return -1, -1
+}

src/NCKUAlg/ProgHW4/knapsack01/test1.txt

+weight value howMany
+50
+10 60 1
+20 100 1
+30 120 1

src/NCKUAlg/ProgHW4/knapsack01/test2.txt

+weight value howMany
+15
+12 4 1
+1 2 1
+4 10 1
+1 1 1
+2 2 1

src/NCKUAlg/ProgHW4/knapsack01/test3.txt

+weight value howMany
+15
+12 4 10
+1 2 10
+4 10 10
+1 1 10
+2 2 10

src/ch16/ch16.1/16.1-1.go

+//Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+introtoalgorithm3ed@gmail.com)
+//
+//This file is a part of introtoalgorithm3ed.
+//
+//introtoalgorithm3ed is a free software; you can redistribute it and/or modify it under the terms of the GNU General 
+//Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) 
+//any later version.
+//
+//This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the 
+//implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 
+//License for more details.
+//
+//You should have received a copy of the GNU General Public License along with this source file; if not, write to the 
+//Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+
+/*Use dynamic programming to solve activity-selection problem*/
+package main
+
+import (
+	"fmt"
+)
+
+type activity struct {
+	start []int
+	fin   []int
+}
+
+func main() {
+	activities := activity{[]int{0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 20}, []int{0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16, 20}} //start and finish time of each activity. 2 fictitious act 0(start 0, fin 0), act 12(start 20, fin 20) are added
+	numOfAct := len(activities.start)
+	cMatrix, whichActKToPick := make([][]int, numOfAct), make([][]int, numOfAct) //Please check the definition of cMatrix on text page 416
+	for i := 0; i < numOfAct; i++ {                                              //initialization
+		cMatrix[i], whichActKToPick[i] = make([]int, numOfAct), make([]int, numOfAct)
+	}
+	/*it should be step==2:c[0,2]=>c[1,3]=>c[2,4]...
+	step==3:c[0,3]=>c[1,4]=>c[2,5]...
+	and finally step==numOfAct-1: c[0,12]
+	*/
+	for step := 2; step < numOfAct; step++ {
+		fmt.Printf("step=%d\n\n", step)
+		for i := 0; i+step < numOfAct; i++ {
+			j := i + step
+			actkAvailable := startAftActiFinFinBefActjStart(i, j, activities) //pick activities that starts after activity i finishes and finishes before activity j starts
+			fmt.Printf("(i,j)=%d,%d\n", i, j)
+			if len(actkAvailable) != 0 {
+				// fmt.Printf("cMatrix:%v\n", cMatrix)
+				fmt.Println("actkAvailable", actkAvailable)
+				maxC, maxK := 0, 0
+				for _, k := range actkAvailable {
+					// fmt.Printf("maxC=%v, cMatrix[%d][%d]=%d, cMatrix[%d][%d]=%d, sum+1=%d\n",maxC,i,k,cMatrix[i][k],k,j,cMatrix[k][j],cMatrix[i][k]+cMatrix[k][j]+1)
+					if cMatrix[i][k]+cMatrix[k][j]+1 > maxC {
+						maxC = cMatrix[i][k] + cMatrix[k][j] + 1
+						maxK = k
+					}
+				}
+				fmt.Printf("maxC, maxK=%d,%d\n", maxC, maxK)
+				cMatrix[i][j], whichActKToPick[i][j] = maxC, maxK //whichActKToPick[i][j] specifies which activity k to pick
+			}
+		}
+	}
+	//traverse matrix whichActKToPick from [0][10] using recursion until reaching whichActKToPick[i][j]==-1
+	fmt.Printf("Optimal(i.e. max) number of mutually compatible activities=%v\n", cMatrix[0][numOfAct-1])
+	mutCompatActSet := getMutCompatActSet(whichActKToPick, 0, numOfAct-1)
+	fmt.Printf("Optimal mutually compatible activities set=%v\n", mutCompatActSet)
+}
+func getMutCompatActSet(whichActKToPick [][]int, i int, j int) []int {
+	result := make([]int, 0)
+	if i+1 < j && whichActKToPick[i][j] != 0 { //cause when whichActKToPick[i][j]==0 it means there's no act k such that it starts after act i finishes and finishes before act j starts
+		//fmt.Println("haha",i,j,whichActKToPick[i][j])
+		result = append(result, whichActKToPick[i][j])
+		result = append(result, getMutCompatActSet(whichActKToPick, i, whichActKToPick[i][j])...)
+		result = append(result, getMutCompatActSet(whichActKToPick, whichActKToPick[i][j], j)...)
+		return result
+	}
+	return result
+}
+
+func startAftActiFinFinBefActjStart(i int, j int, act activity) []int {
+	actAvailable := make([]int, 0)
+	for k := i + 1; k < j; k++ {
+		/*Originally, I think k should start from 1 in case we miss those activities<i, which fit the condition on the following if clause.
+		In order to check whether we'll miss out some activities, suppose we have such a situation in which we'll miss act2(k)<act4(i):
+		|  a4=>i |
+		          | a2=>k |
+		                   | a11=>j |
+		However, I found that this's impossible because act arr is already sorted based on fin time, so fin time of a2 must be ealier than a4.
+		So the situation above is impossible.
+		*/
+		if act.start[k] >= act.fin[i] && act.fin[k] <= act.start[j] { //activity k starts after act i finishes, and it finishes before act k starts
+			actAvailable = append(actAvailable, k)
+		}
+	}
+	return actAvailable
+}

src/projectEuler/1.go

 
 func main() {
 	/*
-	If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these 
-	multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
+		If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these 
+		multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.
 	*/
-	sum3:=(3+(1000/3)*3)*(1000/3)/2.0
-	sum5:=(5+(1000/5-1)*5)*(1000/5-1)/2.0
-	sum15:=(15+(1000/15)*15)*(1000/15)/2.0
-	fmt.Printf("Result:%f\n",sum3+sum5-sum15)
-}
+	sum3 := (3 + (1000/3)*3) * (1000 / 3) / 2.0
+	sum5 := (5 + (1000/5-1)*5) * (1000/5 - 1) / 2.0
+	sum15 := (15 + (1000/15)*15) * (1000 / 15) / 2.0
+	fmt.Printf("Result:%f\n", sum3+sum5-sum15)
+}

src/projectEuler/2.go

 
 func main() {
 	/*
-	Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, 
-	the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
-	By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the 
-	even-valued terms.
+		Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, 
+		the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
+		By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the 
+		even-valued terms.
 	*/
 	/*I find that Fibonnacci sequence has a pattern beginning from 3, namely, (odd,odd,even),(odd,odd,even)......
 	  3, 5, 8, 13, 21, 34, 55, 89, ...
 	  o, o, e, o , o,  e,  o  ,o, e
 	*/
-	var a,b,temp,evenSum,ooeCount uint32=1,2,0,2,0
+	var a, b, temp, evenSum, ooeCount uint32 = 1, 2, 0, 2, 0
 	for i := 0; i < 50; i++ {
-		temp=a+b
-		a=b
-		b=temp
+		temp = a + b
+		a = b
+		b = temp
 		ooeCount++
-		if temp>4*1000000{
-			fmt.Printf("Bigger than 4 million: %d, %d\n",temp,temp%2)
+		if temp > 4*1000000 {
+			fmt.Printf("Bigger than 4 million: %d, %d\n", temp, temp%2)
 			break
 		} else {
-			if ooeCount%3==0{
-				evenSum+=temp
-				fmt.Printf("evenSome increase to:%d\n",evenSum)
+			if ooeCount%3 == 0 {
+				evenSum += temp
+				fmt.Printf("evenSome increase to:%d\n", evenSum)
 			}
 		}
-		fmt.Printf("%d, %d\n",temp,temp%2)
+		fmt.Printf("%d, %d\n", temp, temp%2)
 	}
-	fmt.Printf("Final evenSum=%d\n",evenSum)
-}
+	fmt.Printf("Final evenSum=%d\n", evenSum)
+}

src/projectEuler/3.go

-//Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+introtoalgorithm3ed@gmail.com)
-//
-//This file is a part of introtoalgorithm3ed.
-//
-//introtoalgorithm3ed is a free software; you can redistribute it and/or modify it under the terms of the GNU General 
-//Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) 
-//any later version.
-//
-//This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the 
-//implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 
-//License for more details.
-//
-//You should have received a copy of the GNU General Public License along with this source file; if not, write to the 
-//Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
-
-//Task: Find the number of inversions in the file given. 
-//The file contains all the 100,000 integers between 1 and 100,000 (including both) in some random order(no integer is repeated).
-package main
-
-import (
-	"fmt"
-)
-
-func main() {
-	//The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
-	/*
-	*/
-	var maxPFactor uint32=0
-	fmt.Printf("FMax prime factor=%d\n",maxPFactor)
-}

src/projectEuler/3_v1.go

+//Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+introtoalgorithm3ed@gmail.com)
+//
+//This file is a part of introtoalgorithm3ed.
+//
+//introtoalgorithm3ed is a free software; you can redistribute it and/or modify it under the terms of the GNU General 
+//Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) 
+//any later version.
+//
+//This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the 
+//implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 
+//License for more details.
+//
+//You should have received a copy of the GNU General Public License along with this source file; if not, write to the 
+//Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+
+//Task: Find the number of inversions in the file given. 
+//The file contains all the 100,000 integers between 1 and 100,000 (including both) in some random order(no integer is repeated).
+package main
+
+import (
+	"fmt"
+)
+
+func main() {
+	//The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
+	/*I think I can use dynamic programming, start from finding small prime then divide a bigger number, which we don't 
+	know whether it's prime by these smaller primes(we need to store these).
+	*/
+	//This version is too slow when target==600851475143
+	var target, maxPrimeFactor uint64 = 97, 1
+	smallerPrimes, isPrime := []uint64{2}, true
+	var i uint64 = 3
+	for ; i <= target; i++ {
+		maxPrimeFactor = 1
+		isPrime = true
+		fmt.Println("i", i)
+		for j := len(smallerPrimes) - 1; j > -1; j-- {
+			//fmt.Println("smallPrime", smallerPrimes[j])
+			if i%smallerPrimes[j] == 0 {
+				isPrime = false
+				maxPrimeFactor = smallerPrimes[j]
+				break
+			}
+		}
+		if isPrime {
+			smallerPrimes = append(smallerPrimes, i)
+		}
+	}
+	if target == smallerPrimes[len(smallerPrimes)-1] { //in the condition which target itself is a prime.
+		maxPrimeFactor = target
+	}
+	fmt.Printf("FMax prime factor=%d\n", maxPrimeFactor)
+}

src/projectEuler/3_v2.go

+//Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+introtoalgorithm3ed@gmail.com)
+//
+//This file is a part of introtoalgorithm3ed.
+//
+//introtoalgorithm3ed is a free software; you can redistribute it and/or modify it under the terms of the GNU General 
+//Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) 
+//any later version.
+//
+//This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the 
+//implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 
+//License for more details.
+//
+//You should have received a copy of the GNU General Public License along with this source file; if not, write to the 
+//Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+
+\/*The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?*/
+package main
+
+import (
+	"fmt"
+)
+
+func main() {
+	/*I think I can use dynamic programming, start from finding small prime then divide a bigger number, which we don't 
+	know whether it's prime by these smaller primes(we need to store these).
+	*/
+	//Quadratic sieve algorithm, probably the fastest way for solving target up to 100 digits long: requires large amounts of memory so maybe not try it here
+	//Pollard's rho algorithm(http://en.wikipedia.org/wiki/Pollard's_rho_algorithm)
+	var target, maxPrimeFactor uint64 = 97, 1
+	smallerPrimes, isPrime := []uint64{2}, true
+	var i uint64 = 3
+	for ; i <= target; i++ {
+		maxPrimeFactor = 1
+		isPrime = true
+		fmt.Println("i", i)
+		for j := len(smallerPrimes) - 1; j > -1; j-- {
+			//fmt.Println("smallPrime", smallerPrimes[j])
+			if i%smallerPrimes[j] == 0 {
+				isPrime = false
+				maxPrimeFactor = smallerPrimes[j]
+				break
+			}
+		}
+		if isPrime {
+			smallerPrimes = append(smallerPrimes, i)
+		}
+	}
+	if target == smallerPrimes[len(smallerPrimes)-1] { //in the condition which target itself is a prime.
+		maxPrimeFactor = target
+	}
+	fmt.Printf("FMax prime factor=%d\n", maxPrimeFactor)
+}
+
+func euclideanAlgGCD(a uint64,b uint64) uint64 {
+	for ;a!=b;{
+		switch {				
+			case a>b:
+				a-=b
+			default://a<b
+				b-=a
+		}
+	}
+	return a
+}