65 lines
2.8 KiB
Fortran
65 lines
2.8 KiB
Fortran
program mcnugget
|
|
! Program to find non-McNugget numbers (up to 100) that cannot be expressed as
|
|
! 6x + 9y + 20z (with x, y, z non-negative integers). This version uses dynamic
|
|
! programming to mark expressible numbers and then uses FINDLOC on a logical mask
|
|
! (derived by applying .NOT. to the expressible array) to obtain the largest
|
|
! non-expressible number.
|
|
|
|
implicit none
|
|
integer, parameter :: n = 100
|
|
logical :: expressible(0:n) ! Mark if each number 0:n is expressible.
|
|
integer :: max_val ! To store the largest non-expressible number.
|
|
integer :: i, j ! Loop indices.
|
|
integer :: denoms(3) ! Array of denominations: 6, 9, 20.
|
|
integer, allocatable :: loc(:)
|
|
! 'loc' will store the indices returned by FINDLOC.
|
|
|
|
!--------------------------------------------------------------------
|
|
! Initialize the denominations and print them.
|
|
!--------------------------------------------------------------------
|
|
denoms = [6, 9, 20]
|
|
print *, 'Nugget pacet sizes: ', denoms
|
|
|
|
!--------------------------------------------------------------------
|
|
! Initialize all numbers as non-expressible except 0.
|
|
! 0 is expressible (with x = y = z = 0).
|
|
!--------------------------------------------------------------------
|
|
expressible = .false.
|
|
expressible(0) = .true.
|
|
|
|
!--------------------------------------------------------------------
|
|
! Dynamic programming:
|
|
! For each denomination, if a number i is expressible then mark
|
|
! i + denomination as expressible (provided it does not exceed n).
|
|
!--------------------------------------------------------------------
|
|
do j = 1, 3
|
|
do i = 0, n - denoms(j)
|
|
if (expressible(i)) then
|
|
expressible(i + denoms(j)) = .true.
|
|
end if
|
|
end do
|
|
end do
|
|
|
|
!--------------------------------------------------------------------
|
|
! Instead of looping to count and store non-expressible numbers,
|
|
! we use the FINDLOC intrinsic to get the largest index for which
|
|
! the number is NOT expressible.
|
|
!
|
|
! The expression (.not. expressible) creates a logical mask that is .true.
|
|
! when a number is non-expressible. FINDLOC with BACK=.TRUE. searches the
|
|
! array in reverse order (from n down to 0), thus returning the maximum index.
|
|
!--------------------------------------------------------------------
|
|
loc = findloc(.not. expressible, .true., back = .true.)
|
|
if (size(loc) > 0) then
|
|
max_val = loc(1) ! Retrieve the largest non-expressible number.
|
|
else
|
|
max_val = 0 ! In the unlikely event that every number is expressible.
|
|
end if
|
|
|
|
!--------------------------------------------------------------------
|
|
! Output the result (only the largest non-McNugget number).
|
|
!--------------------------------------------------------------------
|
|
print *, 'Maximum non-McNuggets number is ', max_val
|
|
|
|
end program mcnugget
|