我需要编写一个递归函数,如果整数的数字升序(从左到右(,则返回 1,如果降序返回 -1,如果两者都不返回 0。
我的解决方案尝试每次都返回 0,我知道为什么,但我不知道如何解决它。
这是我的代码:
#include <stdio.h>
int check_order(int n)
{
if (n % 10 > n / 10 % 10)
{
return check_order(n / 10);
if (n == 0)
{
return 1;
}
}
else if (n % 10 < n / 10 % 10)
{
return check_order(n / 10);
if (n == 0)
{
return -1;
}
}
else
{
return 0;
}
}
int main()
{
int n;
printf("enter a whole number (n > 9):");
scanf_s("%d", &n);
printf("function returned: %dn", check_order(n));
}
下面是一个简单的递归:
int f(int n){
if (n < 10)
return 0;
int dr = n % 10; // rightmost digit
n = n / 10;
int dl = n % 10; // second digit from the right
int curr = dl < dr ? 1 : -1; // current comparison
if (dl == dr) curr = 0; // keep strict order
if (n < 10)
return curr;
return curr == f(n) ? curr : 0; // are the comparisons consistent?
}
解释一下你的算法?
假设您使用以下内容:
- 你会得到一个号码。
- 您需要将该数字转换为数字序列。
- 如果给定一个数字,则可以将该数字转换为数字序列。
- 如果给定一个数字序列,请使用 那。
- 比较每对数字 ->升序、降序或两者都不比较。 按
- 顺序/递归方式组合每对的结果。
我们可以使用字符串来简化数字比较,并接受非常长的数字序列。
我们可以使用枚举(erated(类型来表示排序。
你如何组合结果?定义一个组合两个相邻重叠对的顺序的函数,然后就可以组合结果了。
#include <stdio.h>
#include <string.h>
typedef enum { descending=-1, other=0, ascending=1 } order_t;
order_t pair_order(int a, int b) {
if( a < b ) return ascending;
if( a > b ) return descending;
return other;
}
//strict (increasing/decreasing)
order_t strict_order( order_t x, order_t y ) {
if( x == y ) return x;
return other;
}
//monotone (increasing/decreasing)
order_t monotone_order( order_t x, order_t y ) {
if( x == y ) return x;
if( other == x ) return y;
if( other == y ) return x;
return other;
}
order_t check_order( char* p, int remain ) {
//printf("p:%sn",p); //uncomment to watch progress
if( remain<2 ) return other;
if( remain==2 ) return pair_order(p[0], p[1]);
return strict_order( pair_order(p[0], p[1]), check_order(p+1, remain-1) );
//return monotone_order( pair_order(p[0], p[1]), check_order(p+1, remain-1) );
}
char* order_name[] = {
"descending",
"other",
"ascending"
""
};
int main()
{
char line[666] = "none";
while ( strlen(line) > 0 ) {
printf("enter a number (at least 2 digits):");
fgets(stdin,line,sizeof(line)-1);
if( strlen(line) > 0 && line[strlen(line)-1] == 'n' )
line[strlen(line)-1] = ' ';
order_t order = check_order(line);
printf("function returned: (%d)%sn", order, order_name[order+1]);
}
}
我认为您开始走在正确的轨道上,但需要进一步充实您的代码。 我的解决方案借用了@ChuckCottrill,因为我喜欢他的enum
但我不喜欢他不打球(即转换为字符串而不是处理int
(。 我还借用了@ggorlen的不错的测试示例,但我也不喜欢该解决方案,因为当只需要一次传递时,可能需要多次通过数字才能找出答案:
#include <stdio.h>
typedef enum { descending=-1, other=0, ascending=1 } order_t; // a la @ChuckCottrill
order_t check_order(int n)
{
if (n > 9) {
int right = n % 10;
int left = n / 10 % 10;
if (right > left) {
n /= 10;
if (n > 9) {
return (ascending == check_order(n)) ? ascending : other;
}
return ascending;
}
if (right < left) {
n /= 10;
if (n > 9) {
return (descending == check_order(n)) ? descending : other;
}
return descending;
}
}
return other;
}
int main() { // a la @ggorlen
printf("12345: %dn", check_order(12345));
printf("54321: %dn", check_order(54321));
printf("54323: %dn", check_order(54323));
printf("454321: %dn", check_order(454321));
printf("1: %dn", check_order(1));
printf("12: %dn", check_order(12));
printf("21: %dn", check_order(21));
}
输出
> ./a.out
12345: 1
54321: -1
54323: 0
454321: 0
1: 0
12: 1
21: -1
>
适用于任何长度的版本,因为它将字符串作为参数。 并且为递归函数提供先前的状态(升序或降序(允许一些更短的代码和更少的函数。
int check_order(char *str, int index, int previous) {
char current = str[index]; // char at index
char next = str[index+1]; // char at index+1
if (current == 0 || next == 0) {
return previous; // End of string
}
// Ascending or descending?
int status = next > current ? 1 : (next < current ? -1 : 0);
if (status == 0 || index > 0 && status != previous) {
// If neither -1/1 nor status == previous (while not initial call)
return 0;
}
return check_order(str, index+1, status); // Check from next index
}
main函数必须确保字符串至少为 2 个字符
int main(int argc, char **argv) {
char *str = *++argv;
// Some optional checks on str here... (like this is a number)
int status = 0; // Default value if string length < 2
if (strlen(str) >= 2) {
status = check_order(str, 0, 0);
}
printf("Check order for %s is %dn", str, status);
return 0;
}
像这样的return
语句之后的代码是无法访问的:
return check_order(n / 10);
if (n == 0)
{
return -1;
}
除此之外,您正在正确的轨道上检查当前数字与下一个数字,但我没有看到明确的基本情况(当n < 10
时,即个位数(。
尝试在一个递归函数中检查升序和降序很难管理。特别是,在堆栈帧之间通信状态并确定哪些情况在给定调用中仍然有效,这表明返回值已过度工作。
为了省去返回结构或使用枚举或幻数作为标志,我会编写两个通用的帮助程序函数,ascending_digits
和descending_digits
。
#include <stdbool.h>
#include <stdio.h>
bool ascending_digits(int n) {
if (n < 10) return true;
if (n % 10 < n / 10 % 10) return false;
return ascending_digits(n / 10);
}
bool descending_digits(int n) {
if (n < 10) return true;
if (n % 10 > n / 10 % 10) return false;
return descending_digits(n / 10);
}
int check_order(int n) {
if (ascending_digits(n)) return 1;
if (descending_digits(n)) return -1;
return 0;
}
int main() {
printf("12345: %dn", check_order(12345));
printf("54321: %dn", check_order(54321));
printf("54323: %dn", check_order(54323));
printf("454321: %dn", check_order(454321));
printf("1: %dn", check_order(1));
printf("12: %dn", check_order(12));
printf("21: %dn", check_order(21));
return 0;
}
输出:
12345: 1
54321: -1
54323: 0
454321: 0
1: 1
12: 1
21: -1
这些功能不仅更易于单独理解和维护,而且比将它们不可分割地捆绑在一起也更容易重用。
这不会处理负数 - 您可以应用abs
,然后根据需要从那里开始。处理相等的值也是如此;此实现接受1223
等数字,但您可以使用<=
来强制实施严格排序。