Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc6192d7

Browse files
committed
feat: add findLongestRecurringCycle algorithm (Problem 26)
1 parentfd1d6e6 commitc6192d7

File tree

2 files changed

+13
-42
lines changed

2 files changed

+13
-42
lines changed

‎Project-Euler/Problem026.js

Lines changed: 5 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -4,9 +4,6 @@
44
*@see {@link https://projecteuler.net/problem=26}
55
*
66
* Find the value of denominator < 1000 for which 1/denominator contains the longest recurring cycle in its decimal fraction part.
7-
*
8-
* A unit fraction (1/denominator) either terminates or repeats. We need to determine the length of the repeating sequence (cycle)
9-
* for each fraction where the denominator is between 2 and 999, and find the denominator that produces the longest cycle.
107
*/
118

129
/**
@@ -23,49 +20,37 @@ function findLongestRecurringCycle(limit) {
2320
*@returns {number} The length of the recurring cycle in the decimal part of 1/denominator.
2421
*/
2522
functiongetRecurringCycleLength(denominator){
26-
// A map to store the position of each remainder encountered during division
2723
constremainderPositions=newMap()
28-
letnumerator=1// We start with 1 as the numerator (as we're computing 1/denominator)
29-
letposition=0// This tracks the position of each digit in the decimal sequence
24+
letnumerator=1
25+
letposition=0
3026

31-
// Continue until the remainder becomes 0 (terminating decimal) or a cycle is found
3227
while(numerator!==0){
33-
// If the remainder has been seen before, we've found the start of the cycle
3428
if(remainderPositions.has(numerator)){
35-
// The length of the cycle is the current position minus the position when the remainder first appeared
3629
returnposition-remainderPositions.get(numerator)
3730
}
3831

39-
// Record the position of this remainder
4032
remainderPositions.set(numerator,position)
4133

42-
// Multiply numerator by 10 to simulate long division and get the next digit
4334
numerator=(numerator*10)%denominator
44-
position++// Move to the next digit position
35+
position++
4536
}
4637

47-
// If numerator becomes 0, it means the decimal terminates (no cycle)
4838
return0
4939
}
5040

51-
letmaxCycleLength=0// Store the maximum cycle length found
52-
letdenominatorWithMaxCycle=0// Store the denominator corresponding to the longest cycle
41+
letmaxCycleLength=0
42+
letdenominatorWithMaxCycle=0
5343

54-
// Iterate through each possible denominator from 2 up to (limit - 1)
5544
for(letdenominator=2;denominator<limit;denominator++){
56-
// Calculate the cycle length for the current denominator
5745
constcycleLength=getRecurringCycleLength(denominator)
5846

59-
// Update the maximum length and the corresponding denominator if a longer cycle is found
6047
if(cycleLength>maxCycleLength){
6148
maxCycleLength=cycleLength
6249
denominatorWithMaxCycle=denominator
6350
}
6451
}
6552

66-
// Return the denominator that has the longest recurring cycle
6753
returndenominatorWithMaxCycle
6854
}
6955

70-
// Exporting the main function for use in other modules
7156
export{findLongestRecurringCycle}

‎Project-Euler/test/Problem026.test.js

Lines changed: 8 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -4,27 +4,13 @@ import { findLongestRecurringCycle } from '../Problem026'
44
* Tests for the findLongestRecurringCycle function.
55
*/
66
describe('findLongestRecurringCycle',()=>{
7-
// Test to check the basic case with a limit of 10
8-
test('should return 7 for limit of 10',()=>{
9-
constresult=findLongestRecurringCycle(10)
10-
expect(result).toBe(7)
11-
})
12-
13-
// Test to check with a limit of 1000
14-
test('should return the correct value for limit of 1000',()=>{
15-
constresult=findLongestRecurringCycle(1000)
16-
expect(result).toBe(983)// The expected result is the denominator with the longest cycle
17-
})
18-
19-
// Test with a smaller limit to validate behavior
20-
test('should return 3 for limit of 4',()=>{
21-
constresult=findLongestRecurringCycle(4)
22-
expect(result).toBe(3)
23-
})
24-
25-
// Test with a limit of 2, where there is no cycle
26-
test('should return 0 for limit of 2',()=>{
27-
constresult=findLongestRecurringCycle(2)
28-
expect(result).toBe(0)// No cycle for fractions 1/1 and 1/2
7+
it.each([
8+
{limit:10,expected:7},
9+
{limit:1000,expected:983},// The denominator with the longest cycle for limit of 1000
10+
{limit:4,expected:3},
11+
{limit:2,expected:0}// No cycle for fractions 1/1 and 1/2
12+
])('should return $expected for limit of $limit',({ limit, expected})=>{
13+
constresult=findLongestRecurringCycle(limit)
14+
expect(result).toBe(expected)
2915
})
3016
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp