Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #105719

Re: Program to find consecutive integers

Show all headers | View raw

insane_goat <nobody@nothing.net> wrote:
> On 2017-03-10, Joe Pfeiffer <pfeiffer@cs.nmsu.edu> wrote:
> > Umm.... you're going to have to give a more complete description of the
> > problem statement before I, at any rate, will want to think about your
> > program.

> Sorry. I was in a bit of a rush.

> I meant consecutive integers which add up to the target.

That's still underspecified. What's the minimum number of
consecutive integers that must make up the target number?
Your program doesn't seem to be satisfied with only 2, but
all odd numbers (except 1) can be represented as the sum
of two consecutive numbers.

And do you want to find all possible solution or are you
happy when you found the very first one? There are lots
of cases with several solutions, e.g. for 15 you have

1 2 3 4 5
4 5 6
7 8

But your program will only find the first one.

What you definitely can do without is the memory alloca-
tion (and setting it to 0 each round through an inner
loop) - you just have to "remember" the start and the
end of the sequence to print out all the numbers.

And your handling of argv[1] is a bit dangerous. It doesn't
recognize properly when it's no number at all, and for
negative numbers you end up with a huge taget value.

Here's my version of your program. It probably isn't any
faster (but it at least has one less level of loop nesting).
Perhaps one could speed it up a bit by using Gauss' formula
(i.e., the sum of all numbers from 1 to n is n*(n+1)/2) but
I'm too lazy to work it out;-) It also prints out solutions
that consist of two consecutive numbers only and prints
out all possible sequences (which will make it slower than
yours since it does more work).

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int main(int argc, char *argv[])
{
    if (argc < 2) {
        fprintf(stderr, "usage: %s <target>\n", argv[0]);
        return EXIT_FAILURE;
    }

    const char *p = argv[1];
    while (isblank(*p))
        p++;

    if (! *p || ! isdigit(*p)) {
        fprintf(stderr, "target must be a non-negative number\n");
        return EXIT_FAILURE;
    }

    const unsigned target = (unsigned) atoi(p);
    int found = 0;

    for (unsigned begin = 1; begin <= target / 2; ++begin) {
        unsigned end = begin + 1;
        unsigned answer = begin + end;

        while (answer < target)
            answer += ++end;

        if (answer > target)
            continue;

        found++;
        for (unsigned i = begin; i < end; ++i)
            printf("%u ", i);
        printf("%u\n", end);
//      break;            // uncomment to get only the first solution
    }

    if (! found)
        puts("no answer");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}
                     Regards, Jens
-- 
  \   Jens Thoms Toerring  ___      jt@toerring.de
   \__________________________      http://toerring.de

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-10 04:21 +0000
  Re: Program to find consecutive integers Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-03-09 22:26 -0700
    Re: Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-10 06:48 +0000
      Re: Program to find consecutive integers Ike Naar <ike@iceland.freeshell.org> - 2017-03-10 08:18 +0000
        Re: Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-10 08:48 +0000
          Re: Program to find consecutive integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-10 10:38 +0000
            Re: Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-12 13:15 +0000
              Re: Program to find consecutive integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-12 13:29 +0000
            Re: Program to find consecutive integers raltbos@xs4all.nl (Richard Bos) - 2017-03-14 07:49 +0000
          Re: Program to find consecutive integers Öö Tiib <ootiib@hot.ee> - 2017-03-10 05:12 -0800
        Re: Program to find consecutive integers jameskuyper@verizon.net - 2017-03-10 07:16 -0800
          Re: Program to find consecutive integers Ike Naar <ike@iceland.freeshell.org> - 2017-03-10 19:20 +0000
            Re: Program to find consecutive integers James Kuyper <jameskuyper@verizon.net> - 2017-03-10 15:21 -0500
              Re: Program to find consecutive integers Ike Naar <ike@iceland.freeshell.org> - 2017-03-10 20:36 +0000
              Re: Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-12 13:19 +0000
                Gotta keep up with the times (Was: Program to find consecutive integers) gazelle@shell.xmission.com (Kenny McCormack) - 2017-03-12 13:25 +0000
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-12 08:11 -0700
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) gazelle@shell.xmission.com (Kenny McCormack) - 2017-03-12 15:53 +0000
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-12 10:50 -0700
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) gazelle@shell.xmission.com (Kenny McCormack) - 2017-03-12 18:25 +0000
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-12 16:20 -0700
                Re: Gotta keep up with the times gordonb.g2pqz@burditt.org (Gordon Burditt) - 2017-03-14 01:09 -0500
                Re: Gotta keep up with the times raltbos@xs4all.nl (Richard Bos) - 2017-03-14 07:43 +0000
                Re: Program to find consecutive integers "James R. Kuyper" <jameskuyper@verizon.net> - 2017-03-12 10:28 -0400
            Re: Program to find consecutive integers Gareth Owen <gwowen@gmail.com> - 2017-03-11 07:42 +0000
      Re: Program to find consecutive integers jt@toerring.de (Jens Thoms Toerring) - 2017-03-10 10:21 +0000
        Re: Program to find consecutive integers Nathan Wagner <nw@hydaspes.if.org> - 2017-03-10 22:07 +0000
          Re: Program to find consecutive integers Nathan Wagner <nw@hydaspes.if.org> - 2017-03-10 22:20 +0000
          Re: Program to find consecutive integers jr <creature.eternal@gmail.com> - 2017-03-10 23:49 -0800
        Re: Program to find consecutive integers jt@toerring.de (Jens Thoms Toerring) - 2017-03-11 23:38 +0000
          Re: Program to find consecutive integers Tim Rentsch <txr@alumni.caltech.edu> - 2017-04-16 21:18 -0700

csiph-web